UVA11478 Halum （差分约束）

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

最后就是要确定所有的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<bits/stdc++.h>

using namespace std;

//#define LOCAL

const int maxn = ,maxm = ;

int hd[maxn],nx[maxm],to[maxm],d[maxm];

int n,m;

int D[maxn],vis[maxn];

int cnt[maxn];

bool spfa()

{

    stack<int>S;

    memset(cnt,,sizeof(cnt));

    for(int i = ; i <= n; i++) { vis[i] = true; D[i] = .; 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 = ; i < m; i++) d[i] -= x;

    for(int i = ; i <= n; i++) D[i] = ;

    bool fg = spfa();

    for(int i = ; 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,-,sizeof(hd));

        int l = ,r = ;

        for(int i = ; 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+)) { puts("Infinite"); continue; }

        while(l<r){

            int x = (l+r+)>>;

            !P(x)?l = x:r = x-;

        }

        printf("%d\n",l);

    }

    return ;

}