p11478_page-0001.jpg

 

题意：给出一张有向图，每次可以任选一个点和一个整数d，把以它为起点的边权值+d，以它为终点的边权值-d，最终要让所有边权值为正，且边权最小值最大。

最小值最大自然二分。

问题在于如何判断边权最小值为mid的情况是否可行。

差分约束

设点 i 被操作的值的总和 sum[i] 次，点 j 被操作的值总和为 sum[j] ，则边 i->j 的边权为原始边权 w[i][j]+sum[i]−sum[j]≤midw[i] [j] + sum[i] - sum[j]\leq mid，，对每一条边得到一个不等式，转化为 sum[i]−sum[j]≤mid−w[i][j]sum[i]-sum[j]\leq mid-w[i] [j]。

这样的方程组就是差分约束问题，可以看到把sum[i]看作有向图上i到源点的距离d[i]，问题就类似于在有向图上连一条j到i，权值为 mid−w[i][j]mid-w[i] [j] 的边，再把从新建一个超级源点向每个点连权值为0的边，再用Bellman或者SPFA求得每个点到源点的最短路，就是这个方程组的一个可行解。

若有负环则表明方程组无解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const int INF = 1e6;
int n, m;
struct Edge
{
	int from, to, dist;
};

vector<Edge>edges;
vector<int>G[maxn];
bool inq[maxn];
ll d[maxn], p[maxn], cnt[maxn];
void init(int n) {
	for (int i = 1; i <= n; i++) {
		G[i].clear();
	}
	edges.clear();
}
void add_edge(int from, int to, int dist) {
	edges.push_back(Edge{ from,to,dist });
	G[from].push_back(edges.size() - 1);
}
bool negacycle(int x) {
	queue<int>Q;
	memset(inq, 0, sizeof(inq));
	memset(cnt, 0, sizeof(cnt));
	for (int i = 1; i <= n; i++) {
		d[i] = 0;
		inq[i] = true;
		Q.push(i);
	}
	while (!Q.empty()) {
		int u = Q.front(); Q.pop();
		inq[u] = false;
		for (int i = 0; i < G[u].size(); i++) {
			Edge& e = edges[G[u][i]];
			if (d[e.to] > d[u] + e.dist - x) {
				d[e.to] = d[u] + e.dist - x;
				p[e.to] = G[u][i];
				if (!inq[e.to]) {
					Q.push(e.to);
					inq[e.to] = true;
					if (++cnt[e.to] > n)return true;
				}
			}
		}
	}
	return false;
}

int l, r;
int main() {

	while (cin >> n >> m) {
		init(n);
		for (int i = 0; i < m; i++) {
			int u, v, w;
			cin >> u >> v >> w;
			add_edge(u, v, w);
		}
		if (negacycle(1)) {
			cout << "No Solution" << endl;
			continue;
		}
		l = 1; r = 10010;
		while (l < r) {
			int mid = (l + r + 1) / 2;
			if (negacycle(mid))r = mid - 1;
			else l = mid;
		}
		if (l == 10010)cout << "Infinite" << endl;
		else cout << l << endl;
	}
	return 0;
}