原文：点击打开链接
poj1860：点击打开链接
判断是否存在正环。
bellman
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> using namespace std; const int maxn=110; const int maxm=220; double dist[maxn],v,c[maxm][2]; int cnt,n,m,d[maxm][2],s; int bellman() { for(int i=1;i<=n;i++) dist[i]=0; dist[s]=v; for(int i=0;i<n-1;i++) { int flag=0; for(int j=0;j<cnt;j++) { int u=d[j][0]; int v=d[j][1]; if(dist[v]<(dist[u]-c[j][1])*c[j][0]) { dist[v]=(dist[u]-c[j][1])*c[j][0]; flag=1; } if(!flag) break; } } for(int j=0;j<cnt;j++){ int u=d[j][0]; int v=d[j][1]; if(dist[v]<(dist[u]-c[j][1])*c[j][0]) return 1; } return 0; } int main() { while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF) { int a,b; cnt=0; double x,y,e,f; for(int i=0;i<m;i++) { scanf("%d%d%lf%lf%lf%lf",&a,&b,&x,&y,&e,&f); d[cnt][0]=a; d[cnt][1]=b; c[cnt][0]=x; c[cnt][1]=y; cnt++; d[cnt][0]=b; d[cnt][1]=a; c[cnt][0]=e; c[cnt][1]=f; cnt++; } if(bellman()) printf("YES\n"); else printf("NO\n"); } return 0; } spfa #include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <queue> #define inf 1e6 using namespace std; struct node { int v; double c,r; }; node edge[3000]; double dist[3000],v1; int cnt,n,m,s,vis[3000],num[3000],next[3000],f[3000]; int spfa() { queue<int> q; for(int i=0;i<=n;i++) dist[i]=0; dist[s]=v1; q.push(s);vis[s]=1;num[s]++; while(!q.empty()) { int x; x=q.front();q.pop();vis[x]=0; for(int i=f[x];i!=-1;i=next[i]) { if(dist[edge[i].v]<(dist[x]-edge[i].c)*edge[i].r) { dist[edge[i].v]=(dist[x]-edge[i].c)*edge[i].r; if(!vis[edge[i].v]) { vis[edge[i].v]=1; q.push(edge[i].v); num[edge[i].v]++; } if(num[edge[i].v]>n) { return 1; } } } } return 0; } int main() { while(scanf("%d%d%d%lf",&n,&m,&s,&v1)!=EOF) { memset(f,-1,sizeof(f)); memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); cnt=0; for(int i=0;i<m;i++) { int a,b; double c,d,e,x; scanf("%d%d%lf%lf%lf%lf",&a,&b,&c,&d,&e,&x); // edge[cnt].u=a; edge[cnt].v=b; edge[cnt].r=c; edge[cnt].c=d; next[cnt]=f[a]; f[a]=cnt; cnt++; // edge[cnt].u=b; edge[cnt].v=a; edge[cnt].r=e; edge[cnt].c=x; next[cnt]=f[b]; f[b]=cnt; cnt++; } if(spfa()) printf("YES\n"); else printf("NO\n"); } return 0; }