题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2473
题解:
首先我们可以得到的约束条件形如 xi - xj <= b[k] ,即可以转换为 j - > i连边，且权值为b[k]，这样建图后我们判断是否有解，只需要用spfa跑负圈就可以了.
如果存在负圈，原差分系统定然无解.
简单证明:
我们不妨设这个环为 x1,x2...xn
即有不等式 x1 <= x2 + y1 , x2 <= x3 + y2 ..... xn <= x 1 + yn
全部累加得 0 <= sigma (y)
所以有解必须满足sigma(y) >= 0 ,如果存在负圈，肯定是无解的.
那么对于原图，如何判断infinate的情况呢？
注意到约束条件必须是环，所以我们只需要检测一下图中是否有环就可以了.
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 5e2 + 50; const double eps = 1e-6; struct Edge{int v , nxt , w;}; Edge e[maxn * 6]; int n , m , head[maxn] , tot , cnt[maxn] ,inq[maxn] ,d[maxn],c[maxn]; queue<int>q; void addedge(int u,int v,int w){e[tot].v=v,e[tot].nxt=head[u],e[tot].w=w,head[u]=tot++;} void edge_init(int x) { for(int i = 0 ; i < tot ; ++ i) e[i].w += x; } bool check() { while(!q.empty()) q.pop(); memset(cnt , 0 , 4 * (n + 1)); memset( d , 0 , 4 * (n + 1) ); for(int i = 1 ; i <= n ; ++ i) { inq[i] = 1; q.push(i); } while(!q.empty()) { int x = q.front();q.pop();inq[x]=0; for(int i = head[x] ; ~i ; i = e[i].nxt) { int v = e[i].v; double neww = d[x] + e[i].w; if(neww < d[v]) { d[v] = neww; if(!inq[v]) { inq[v] = 1; if(++cnt[v] > n) return true; q.push(v); } } } } return false; } bool dfs(int u) { c[u]=-1; for(int i = head[u] ; ~i ; i = e[i].nxt) { int v = e[i].v; if(c[v]==1) continue; if(c[v]==-1) return true; if(dfs(v)) return true; } c[u]=1; return false; } int main(int argc,char *argv[]) { while(~scanf("%d%d",&n,&m)) { memset(head,-1,4*(n+1));tot=0;memset(c , 0 , 4 * (n + 1)); for(int i = 0 ; i < m ; ++ i) { int u ,v,w ;scanf("%d%d%d",&u,&v,&w); addedge( u , v, w); } int flag = 0; for(int i = 1 ; i <= n ; ++ i) if(c[i]==0) if(dfs(i)) { flag=1; break; } if(!flag) { printf("Infinite "); continue; } int L = 0 , R = 20000; while(L < R) { int mid = L + (R-L+1)/2; edge_init(-mid); if(check()) R = mid-1; else L = mid; edge_init(mid); } edge_init(-L); if(L == 0 || check()) printf("No Solution "); else printf("%d ",L); } return 0; }