poj3259
题目大意 一个图，存在某些边是负，问是否存在负环
注意 题中没有给定起点，但我看别人的AC代码有的是dist[1]=0.其实这样是不必要的，题中并没有说是从1出发。我第一次写的是运行了n次bellmanford来判断从每个点出发是否有环，结果超时.bellmanford在不初始化起点的情况下，可以用来判断图是否存在环（即使不是连通图） 代码中采用链式前向星的写法
代码
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> using namespace std; const int INF=999999999; int F; int N,M,W; int S,E,T; struct Edge { int to; int next; int cost; }edge[6000]; int edgenum=0; int dist[600]; int Head[600]; void Add_Edge(int u,int v,int t)//增加从u到v的单向边 { edge[++edgenum].to=v; edge[edgenum].cost=t; edge[edgenum].next=Head[u]; Head[u]=edgenum; } bool Bellman_Ford()//存在负环返回1 { for(int i=1;i<=N;i++)dist[i]=INF; //这里可以不用初始化起点 for(int i=1;i<N;i++) { for(int j=1;j<=N;j++) { for(int k=Head[j];k!=-1;k=edge[k].next) { if(dist[edge[k].to] > dist[j] + edge[k].cost) { dist[edge[k].to] = dist[j] + edge[k].cost; } } } } for(int i=1;i<=N;i++) { for(int k=Head[i];k!=-1;k=edge[k].next) { if(dist[edge[k].to] > dist[i] + edge[k].cost)return 1; } } return 0; } int main() { scanf("%d",&F); for(int i=1;i<=F;i++) { memset(Head,-1,sizeof(Head)); edgenum=0; scanf("%d%d%d",&N,&M,&W); for(int i=1;i<=M;i++) { scanf("%d%d%d",&S,&E,&T); Add_Edge(S,E,T); Add_Edge(E,S,T); } for(int i=1;i<=W;i++) { scanf("%d%d%d",&S,&E,&T); Add_Edge(S,E,-T); } if(Bellman_Ford())printf("YES\n"); else printf("NO\n"); } }