每次操作是独立的，而且顺序并不影响，作用在同一个结点上的d可以叠加，所以令x(u) = sigma(d_ui).

最后就是要确定所有的x(u)。

因为m越大，满足条件的边就越少，二分答案m。

对于一条边a->b，可以列出一个不等式d(a,b) +x(a)-x(b)>=m，移项可得x(b)-x(a)<=d(a,b)-m

正好满足差分约束的形式。所有的边就对应着一个差分约束系统。

差分约束有解的充要条件是不存在负环。

证明：

x(b)-x(a)<=-c,c>0，意味着x(a)至少比x(b)大c，

因为不等式的传递性，如果x(a)在一个负环上，那么意味着x(a)>x(a)，这是矛盾的。

 

因为一开始图不一定连通，可以加一个源点和其他所有点相连，边权为0，用源点的距离表示x(i)的值，

或者sfpa的时候把所有的点加入栈中(判负环用stack比较快)

#include
     
      using namespace std;//#define LOCALconst int maxn = 501,maxm = 2705;int hd[maxn],nx[maxm],to[maxm],d[maxm];int n,m;int D[maxn],vis[maxn];int cnt[maxn];bool spfa(){    stack
      
       S;    memset(cnt,0,sizeof(cnt));    for(int i = 1; i <= n; i++) { vis[i] = true; D[i] = 0.; S.push(i); }    while(S.size()){        int u = S.top(); S.pop();        vis[u] = false;        for(int i = hd[u]; ~i; i = nx[i]){            int v = to[i];            if(D[v]>D[u]+d[i]){                D[v] = D[u]+d[i];                if(!vis[v]){                    S.push(v); vis[v] = true;                    if(++cnt[v] > n) return true;                }            }        }    }    return false;}bool P(int x){    for(int i = 0; i < m; i++) d[i] -= x;    for(int i = 1; i <= n; i++) D[i] = 0;    bool fg = spfa();    for(int i = 0; i < m; i++) d[i] += x;    return fg;}int main(){#ifdef LOCAL    freopen("in.txt","r",stdin);#endif    while(~scanf("%d%d",&n,&m)){        memset(hd,-1,sizeof(hd));        int l = 1,r = 0;        for(int i = 0; i < m; i++){            int u; scanf("%d%d%d",&u,to+i,d+i);            nx[i] = hd[u];            hd[u] = i;            r = max(r,d[i]);        }        if(P(l)) { puts("No Solution"); continue; }        if(!P(r+1)) { puts("Infinite"); continue; }        while(l
       
        >1;            !P(x)?l = x:r = x-1;        }        printf("%d\n",l);    }    return 0;}