uva 558 Wormholes

算是模板题，给定一个有向图，顶点从0到n-1编号，必须从0开始出发，问是否存在负环

一开始写了一个Bellman-Ford，超时，然后就放弃了，写了个spfa的bfs版本，过了，然后又写了一个spfa的dfs版本，wa，然后改了一个下午，还是wa

然后上网找了一下代码，发现很多人写的都是BF算法，看了一下自己的一样，怎么会超时呢？？

后来才发现，我读错题意了，我本来是理解为只要图中有负环就好了，所有枚举了所有的顶点作为源点去BF，所以才超时，现在是规定了0作为源点，所以就AC了

然后就把spfa的dfs版本改了一下，不要枚举所有源点，规定0为源点，然后就AC了，再修改了一些细节地方，跑出了最好成绩0.008排名第5

从这个地方可以看出，数据中，有的图是不连通的，所以有的连通分量有负环有的没有，如果枚举了所以的源点的话，有可能会WA

 

但是有个地方比较困惑，我第一次写spfa的bfs版本的时候也是枚举了所有源点的，可以AC，照理来说应该是WA的，然后改为单源点后也是AC，是数据问题？？不可能啊

希望有人指点一下

 

下面给出代码

 

Bellman-Ford

#include 
#include 
#define N 1010
#define M 2010
#define INF 0x3f3f3f3f
int d[N],u[M],v[M],w[M];
int n,m;int BF(int s)  //Bellman-Ford
{int k,i,j;for(i=0; iINF;d[s]=0;for(k=1; k//进行V-1次松弛for(int i=0; i//枚举所有的边
        {int x=u[i],y=v[i];if( d[x]+w[i] < d[y] )d[y]=d[x]+w[i];}int OK=1;for(int i=0; i//检查一遍所有的边
    {int x=u[i],y=v[i];if( d[x]+w[i] < d[y] )  //还能进行松弛
        {OK=0;break;}}return OK;
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0; i)scanf("%d%d%d",&u[i],&v[i],&w[i]);if(!BF(0))  //有负环printf("possible
");elseprintf("not possible
");}return 0;
}

 

SPFA_BFS

#include 
#include 
#include 
using namespace std;
#define N 1010
#define NN 5
#define M 2010
#define INF 0x3f3f3f3f
int n,m;
int d[N],f[N],nnext[M],u[M],v[M],w[M];  //用数组来模拟邻接表，并且使用头插法
int c[N];  //记录每个顶点进队的次数
bool vis[N];  //标记顶点在队内void input()
{scanf("%d%d",&n,&m);memset(f,0,sizeof(f));//memset(nnext,0,sizeof(nnext));for(int i=1; i<=m; i++)  //边集数组从下标1保存到m
    {scanf("%d%d%d",&u[i],&v[i],&w[i]);nnext[i]=f[u[i]];  //头插法f[u[i]]=i;        //头插法
    }
/*printf("打印邻接表:
");for(int i=0; i*/return ;
}int spfa_bfs(int s)
{queue <int> q;memset(d,0x3f,sizeof(d));d[s]=0;memset(c,0,sizeof(c));memset(vis,0,sizeof(vis));q.push(s);  vis[s]=1; c[s]=1;//顶点入队vis要做标记，另外要统计顶点的入队次数int OK=1;while(!q.empty()){int x;x=q.front(); q.pop();  vis[x]=0;//队头元素出队，并且消除标记for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表
        {int y=v[k];if( d[x]+w[k] < d[y]){d[y]=d[x]+w[k];  //松弛if(!vis[y])  //顶点y不在队内
                {vis[y]=1;    //标记c[y]++;      //统计次数q.push(y);   //入队if(c[y]>NN)  //超过入队次数上限，说明有负环return OK=0;}}}}return OK;}
int main()
{int T;scanf("%d",&T);while(T--){input();if(!spfa_bfs(0))  //有负环printf("possible
");elseprintf("not possible
");}return 0;
}

 

SPFA_DFS

//时间最快0.008
#include 
#include 
#define N 1010
#define M 2010
#define INF 0x3f3f3f3f
int d[N],f[N];
bool vis[N];
struct edge
{int u,v,w,next;}e[M];
int n,m;void input()
{scanf("%d%d",&n,&m);memset(f,0,sizeof(f));for(int i=1; i<=m; i++)  //读入所有边
    {scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);int u=e[i].u;e[i].next=f[u];f[u]=i;}
/*printf("打印邻接表：
");for(int i=0; i*/return ;
}int spfa_dfs(int u)
{vis[u]=1;for(int k=f[u]; k!=0; k=e[k].next){int v=e[k].v,w=e[k].w;if( d[u]+w < d[v] ){d[v]=d[u]+w;if(!vis[v]){if(spfa_dfs(v))return 1;}elsereturn 1;}}vis[u]=0;return 0;
}
int main()
{int T;scanf("%d",&T);while(T--){input();for(int i=0; i){ vis[i]=0; d[i]=INF;}d[0]=0;if(spfa_dfs(0))  printf("possible
");else     printf("not possible
");}return 0;
}    

 

求指教  SPFA_BFS  枚举所有起点，按道理应该是WA的，为什么AC了…………

#include 
#include 
#include 
using namespace std;
#define N 1010
#define NN 5
#define M 2010
#define INF 0x3f3f3f3f
int n,m;
int d[N],f[N],nnext[M],u[M],v[M],w[M];  //用数组来模拟邻接表，并且使用头插法
int c[N];  //记录每个顶点进队的次数
bool vis[N];  //标记顶点在队内void input()
{scanf("%d%d",&n,&m);memset(f,0,sizeof(f));//memset(nnext,0,sizeof(nnext));for(int i=1; i<=m; i++)  //边集数组从下标1保存到m
    {scanf("%d%d%d",&u[i],&v[i],&w[i]);nnext[i]=f[u[i]];  //头插法f[u[i]]=i;        //头插法
    }
/*printf("打印邻接表:
");for(int i=0; i*/return ;
}int spfa_bfs(int s)
{queue <int> q;memset(d,0x3f,sizeof(d));d[s]=0;memset(c,0,sizeof(c));memset(vis,0,sizeof(vis));q.push(s);  vis[s]=1; c[s]=1;//顶点入队vis要做标记，另外要统计顶点的入队次数int OK=1;while(!q.empty()){int x;x=q.front(); q.pop();  vis[x]=0;//队头元素出队，并且消除标记for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表
        {int y=v[k];if( d[x]+w[k] < d[y]){d[y]=d[x]+w[k];  //松弛if(!vis[y])  //顶点y不在队内
                {vis[y]=1;    //标记c[y]++;      //统计次数q.push(y);   //入队if(c[y]>NN)  //超过入队次数上限，说明有负环return OK=0;}}}}return OK;}
int main()
{int T;scanf("%d",&T);while(T--){input();int s;for(s=0; s//枚举所有源点
        {int tmp=spfa_bfs(s) ;//for(int i=0; i//printf("%d ",d[i]);//printf("
");if(!tmp)  break;}if(s//有负环printf("possible
");elseprintf("not possible
");}return 0;
}