差分约束。
这题只需要说明是否存在环即可。距离确定的点可以用S[a] - S[b] <=len, S[b] - S[a] <= len来建。
然后以0点作为源点求最短路即可，判断是否有环。
我还是SPFA用着比较顺。。。就一直用的SPFA。。。
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 1010 using namespace std; typedef struct STA{ int to,len; STA *next; }STA; STA *s[MAX],node[MAX*200]; int n,cou; void init() { memset(s,'/0',sizeof(s)); memset(node,'/0',sizeof(node)); cou = 0; } void Add(int u,int v,int len) { node[cou].to = v; node[cou].len = len; node[cou].next = s[u]; s[u] = &node[cou++]; } int SPFA() { queue<int> Q; int i,len,to,x,inq[MAX],times[MAX],dis[MAX]; STA *head; memset(inq,0,sizeof(inq)); memset(times,0,sizeof(times)); for(i=0; i<=n; i++) dis[i] = INT_MAX; Q.push(0); inq[0] = times[0] = 1; dis[0] = 0; while( !Q.empty() ) { x = Q.front(); Q.pop(); inq[x] = 0; head = s[x]; while( head != NULL ) { to = head->to; len = head->len; if( dis[to] > dis[x] + len ) { dis[to] = dis[x] + len; if( !inq[to] ) { Q.push(to); inq[to] = 1; times[to]++; if( times[to] > n ) return -1; } } head = head->next; } } return 0; } int main() { char ch; int m,i,ans,from,to,len; while( scanf("%d%d",&n,&m) != EOF ) { init(); while(m--) { getchar(); scanf("%c",&ch); if( ch == 'P' ) { scanf("%d%d%d",&from,&to,&len); Add(to,from,len); Add(from,to,-len); } if( ch == 'V' ) { scanf("%d%d",&from,&to); Add(from,to,-1); } } for(i=1; i<=n; i++) Add(0,i,0); //因为下标与在左在右没啥关系，所以只需和源点联系即可。 ans = SPFA(); if( ans == -1 ) printf("Unreliable/n"); else printf("Reliable/n"); } return 0; }
