[DFS]zoj 3583：Simple Path

 

大致题意：
  给出一个无向图和两个点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;
}

 

评论

2 楼 暴风雪 2012-03-31  

cliffbaby 写道

麻烦楼主 再去提交下代码，我提交你的 同样超时！

网上用dfs的代码都超时了现在，zoj加数据了……很容易想象，如果起点一端直接连到终点，另一端连着一个完全图，dfs就必然过不了。必须用网络流神马的才能过

1 楼 cliffbaby 2012-03-31  

麻烦楼主 再去提交下代码，我提交你的 同样超时！