思路：
设dis[i]为标号为i的点到0号点的距离。对于P A B X，我们能得到等式dis[a]-dis[b]=x,那么可以化为两个不等式dis[a]-dis[b]>=x和dis[b]-dis[a]>=-x。这样就可以建两条边。V A B的话，我们知道dis[a]-dis[b]>=1，可以建一条边。这些边建起来后，图可能是一个离散的图，那么我们就定义一个超级源点连接所有的点，权值为0.进行求最长路时，只要判断是否有正圈存在，正圈的含义是绕着这个圈使每个点的dis值不断增大。用bellman-ford算法就行。还有一个笨的方法，其实是卡数据的，我们就用spfa求最长路，若循环次数超过一定，我们就认为有正圈存在。
这个是用bellman_ford做的：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define inf 1<<30 #define Maxn 10010 #define Maxm 500000 using namespace std; int dis[Maxn],vi[Maxn],index[Maxn],e,Que[1000010],num=0,n; struct Edge{ int to,next,val,from; }edge[Maxm]; void init() { int i,j; for( i=0;i<=Maxn-1;i++) dis[i]=-inf; memset(vi,0,sizeof(vi)); memset(index,-1,sizeof(index)); e=0; num=0; } void addedge(int from,int to,int val) { edge[e].from=from; edge[e].to=to; edge[e].val=val; edge[e].next=index[from]; index[from]=e++; } int bellman_ford() { int i,j,temp,flag; for(i=1;i<=n;i++) { flag=1; for(j=0;j<e;j++) { temp=edge[j].from; if(dis[temp]+edge[j].val>dis[edge[j].to]) { dis[edge[j].to]=dis[temp]+edge[j].val; flag=0; } } if(flag) return 1; } return 0; } int main() { int i,j,a,b,c,m; char str[2]; while(scanf("%d%d",&n,&m)!=EOF) { init(); //cout<<"ok"<<endl; for(i=1;i<=m;i++) { scanf("%s",&str); if(str[0]=='P') { scanf("%d%d%d",&a,&b,&c); addedge(b,a,c); addedge(a,b,-c); } else { scanf("%d%d",&a,&b); addedge(b,a,1); } } for(i=1;i<=n;i++) addedge(0,i,0); if(bellman_ford()) printf("Reliable "); else printf("Unreliable "); } return 0; }
给个卡数据的spfa：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define inf 1<<30 #define Maxn 10010 #define Maxm 500000 using namespace std; int dis[Maxn],vi[Maxn],index[Maxn],e,Que[1000010],num=0; struct Edge{ int to,next,val; }edge[Maxm]; void init() { int i,j; for( i=0;i<=Maxn-1;i++) dis[i]=-inf; memset(vi,0,sizeof(vi)); memset(index,-1,sizeof(index)); e=0; num=0; } void addedge(int from,int to,int val) { edge[e].from=from; edge[e].to=to; edge[e].val=val; edge[e].next=index[from]; index[from]=e++; } int spfa() { int i,j,temp,head,rear; head=rear=0; Que[head++]=0; dis[0]=0; //cout<<maxn<<endl; while(head!=rear) { temp=Que[rear++]; //cout<<temp<<endl; vi[temp]=0; for(i=index[temp];i!=-1;i=edge[i].next) { int now=edge[i].to; if(dis[now]<dis[temp]+edge[i].val) { num++; if(num>500000) return 0; if(edge[i].val<0) { dis[temp]+edge[i].val+graphic[now][temp] } dis[now]=dis[temp]+edge[i].val; if(!vi[now]) Que[head++]=now; vi[now]=1; } } } return 1; } int main() { int i,j,n,a,b,c,m; char str[2]; while(scanf("%d%d",&n,&m)!=EOF) { init(); //cout<<"ok"<<endl; for(i=1;i<=m;i++) { scanf("%s",&str); if(str[0]=='P') { scanf("%d%d%d",&a,&b,&c); addedge(b,a,c); addedge(a,b,-c); } else { scanf("%d%d",&a,&b); addedge(b,a,1); } } for(i=1;i<=n;i++) addedge(0,i,0); if(spfa()) printf("Reliable "); else printf("Unreliable "); } return 0; }