题目链接：http://acm.uestc.edu.cn/#/problem/show/1638

题意：
给定n个点（点权未知）和m条信息：u的权值>=v的权值+w
求点权的极小解和极大解（无解则输出-1）

极小解即每个点的点权可能的最小值
极大解即每个点的点权可能的最大值

数据范围：
1<=n<=100000
1<=m<=1000000
0<=w<=100
点权为0到100之间的整数

题解：
差分约束。
求最大值，跑最短路，建一条从v到u权值为w的边。
求最小值，跑最长路，建一条从u到v权值为-w的边。



#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+7; const int maxm = 1e6+7; struct edge{ int v, w, next; edge(int v=0, int w=0, int next=0):v(v),w(w),next(next){} }E1[2*maxm], E2[2*maxm]; int head1[maxn], head2[maxn], cnt1, cnt2; int n, m, cnt[maxn], inq[maxn], mx[maxn], mi[maxn], Q[maxn]; void init(){ memset(head1, -1, sizeof(head1)); memset(head2, -1, sizeof(head2)); cnt1 = cnt2 = 0; } void add(int u, int v, int w, int op) { if(op&1){ E1[cnt1]=edge(v,w,head1[u]), head1[u]=cnt1++; } else{ E2[cnt2]=edge(v,w,head2[u]), head2[u]=cnt2++; } } bool spfa1(){ int top = 0; memset(mi, -1, sizeof(mi)); mi[0] = 0; cnt[0] = 1; inq[0] = 1; Q[top++] = 0; while(top){ int u = Q[--top]; inq[u] = 0; for(int i = head1[u]; ~i; i = E1[i].next){ int v = E1[i].v, w = E1[i].w; if(mi[v] < mi[u] + w){ mi[v] = mi[u] + w; if(inq[v]) continue; if(cnt[v] > n) return 0; cnt[v]++; inq[v] = 1; Q[top++] = v; } } } return 1; } bool spfa2(){ int top = 0; memset(mx, 0x3f, sizeof(mx)); memset(inq, 0, sizeof(inq)); memset(cnt, 0, sizeof(cnt)); mx[0] = 100; cnt[0] = 1; inq[0] = 1; Q[top++] = 0; while(top){ int u = Q[--top]; inq[u] = 0; for(int i = head2[u]; ~i; i=E2[i].next){ int v = E2[i].v, w = E2[i].w; if(mx[v] > mx[u] + w){ mx[v] = mx[u] + w; if(inq[v]) continue; if(cnt[v] > n) return 0; cnt[v]++; inq[v] = 1; Q[top++] = v; } } } for(int i=1; i<=n; i++){ if(min(mi[i],mx[i])<0 || max(mi[i],mx[i])>100) return 0; } return 1; } int main() { init(); scanf("%d %d", &n,&m); for(int i = 1; i <= m; i++){ int u, v, w; scanf("%d %d %d", &u,&v,&w); add(v, u, w, 1); add(u, v, -w, 2); } for(int i = 1; i <= n; i++){ add(0, i, 0, 1); add(0, i, 0, 2); } if(spfa1()&&spfa2()) { for(int i = 1; i <= n; i++){ printf("%d %d\n", mi[i], mx[i]); } } else{ puts("-1"); } return 0; }