【模板】差分约束

题目描述:

现在，有N个变量\(A_1，A_2，A_3，A_4，A_5，…，A_N\)以及M个表达式\(A_{k[i]}-A_{l[i]}<=m[i]\)。
求\(A_N-A_1\)的最大值。

输入格式:

第1行2个数N，M。
接下来M行3个数k[i]，l[i]，m[i]。

输出格式:

若有解，输出最大值。

否则输出No Solution。

若最大值为无限大则输出INF。

样例输入:

样例1
3 3
2 1 3
3 2 2
3 1 6
样例2
4 3
2 1 3
3 2 2
3 1 6
样例3
2 2
1 2 -1
2 1 -1

样例输出:

样例1
5
样例2
INF
样例3
No Solution

提示:

 N<=30000,M<=160000

-40000<=m[i]<=40000

对于测试点0-8，N<=7，M<=7 (30%)

对于测试点9-18，图是DAG (33%)

对于测试点19-24，图是随机图 (20%)

对于测试点25-29，图是一个有向环，边权均为-1 (17%)

\(\color{white}{\text{“我卡我自己”}}\)

本题可以开O2优化

时间限制: 500ms
空间限制: 256MB

---

来源: by qq1010903229