sgu298：King Berl VI(差分约束)

题目大意：

       有  n  个变量  xi  ，  m  个形如  xi≥xj+c  的不等式 ( c并不一定为同一值 ) ，且 xi∈[−10000,10000] ，求一组解使得  xn−xi  的值最小，若无解输出 −1 。

分析：

       不会差分约束的先看看http://ycool.com/post/m2uybbf

       对于  xi≥xj+c  ，我们连边  (j,i)  ，且边权为  c  。对于  xi∈[−10000,10000]  ，增添一个零点和每个点之间连  −10000  的双向边， 跑  1  到  n  的最长路即可。

       卡了我两个小时的常数。。。

AC code：

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define X first
#define Y second
#define clr(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
typedef long long LL;
typedef double DB;
typedef long double LD;
using namespace std;

void open_init()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios::sync_with_stdio();
}

void close_file()
{
    #ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    #endif
}

const int MAXN = ;
const int MAXM = ;
const int INF = ;

int size = ;
int head[MAXN];
int to[MAXM<<];
int w[MAXM<<];
int ne[MAXM<<];
inline void add_edge(int u, int v, int d)
{
    to[size] = v, w[size] = d, ne[size] = head[u], head[u] = size++;
}

int n, m;
bool vis[MAXN];
int dis[MAXN];
int cur[MAXN];
int st[MAXN];

bool spfa(int s, int t)
{
    int top = ;
    clr(dis, -INF);
    memcpy(cur, head, sizeof cur);
    st[++top] = s, dis[s] = , vis[s] = true;
    while(top)
    {
        int now = st[top], next = ;
        for(int &i = cur[now]; i; i = ne[i])
        {
            int T = to[i], W = w[i];
            if(dis[T] < dis[now]+W)
            {
                dis[T] = dis[now]+W;
                if(!vis[T])
                {
                    vis[T] = true;
                    next = T;
                    break;
                }
                else return false;
            }
        }
        if(!cur[now])
        {
            top--;
            cur[now] = head[now];
            vis[now] = false;
        }
        if(next) st[++top] = next;
    }
    return true;
}

int main()
{
    open_init();

    scanf("%d%d", &n, &m);
    rep(i, , m)
    {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        add_edge(v, u, c);
    }
    rep(i, , n)
        add_edge(n+, i, -),
        add_edge(i, n+, -);
    if(!spfa(, n)) puts("-1");
    else
        rep(i, , n)
            printf("%d ", dis[i]-dis[n+]);

    close_file();
    return ;
}