大致题意:
给出一个无向图和两个点s,t。求存在多少点,这些点不在从s到t的简单路上。
大致思路:
比赛时犯傻,上来就把这题当作图的双连通分量来做。后来发现错误,写了一个很暴力的dfs,TLE了,大圣也证明了,dfs很有可能是会超时的,只好作罢。赛后发现居然有人用dfs给水过去了,仔细看了一下居然和我的代码几乎一样,只不过用的是邻接矩阵,我用的是邻接表。遂把我的代码重构一遍,也过去了。
总结:1,数据很水,dfs都能过。
2,数据专门卡邻接表构图。
3,以后比赛时要尽量多试试。
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
int n,m;
bool g[111][111];
bool vis[111];
bool isval[111];int s,t;
int dfs(int loc){
int i;bool flag=0;
if(isval[loc]==1)
return 1;
for(i = 0;i < n;i++){
if(g[loc][i] && !vis[i]){
vis[i]=1;
if(dfs(i)==1){
isval[loc]=1;
s=1;
}
vis[i]=0;
}
}
return flag;
}
int main(){
int i,a,b,ans;
while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF){
ans=n;
memset(g,0,sizeof(g));
memset(isval,0,sizeof(isval));
while(m--){
scanf("%d%d",&a,&b);
g[a][b] = g[b][a] = 1;
}
memset(vis,0,sizeof(vis));
vis[s]=1;
isval[t]=1;
dfs(s);
for(i=0;i<n;i++){
if(isval[i]){
ans--;
}
}
printf("%d\n",ans);
}
return 0;
}
下面是我超时的代码
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=1010;
const int mMax=1010*1010*2;
class edge{
public:
int u,v,nex;
bool live;
};edge e[mMax];
int k,head[nMax];
int vis[nMax];
int isval[nMax],s,t;
void addedge(int a,int b){
// cout<<"add"<<a<<" "<<b<<endl;
e[k].u=a;
e[k].v=b;
e[k].nex=head[a];
head[a]=k;k++;
}
int dfs(int loc){
int i,j,k,a,b,flag=0;
if(isval[loc]==1){
return 1;
}
for(i=head[loc];i;i=e[i].nex){
int v=e[i].v;
if(!vis[v]){
vis[v]=1;
if(dfs(v)==1){
isval[loc]=1;
flag=1;
}
vis[v]=0;
}
}
return flag;
}
int main(){
int n,m,i,j,a,b,ans;
while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF){
k=1;
s++,t++;
ans=n;
memset(isval,0,sizeof(isval));
memset(head,0,sizeof(head));
while(m--){
scanf("%d%d",&a,&b);
a++,b++;
addedge(a,b);
addedge(b,a);
}
memset(vis,0,sizeof(vis));
vis[s]=1;
isval[t]=1;
dfs(s);
for(i=1;i<=n;i++){
if(isval[i]){
ans--;
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
zoj 1255 The Path.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
notes_for_zoj:打算转码的菜鸟,记录一下自己的刷题笔记〜
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj吐血制作,希望大家喜欢