XieNaoban's Blog
0%

有上下界的网络流笔记

发表于 更新于 分类于 阅读次数： 评论次数：
本文字数： 6k 阅读时长 ≈ 5 分钟

从大佬的博客里学到了很多东西，以下是自己的小总结。

无源汇有上下界可行流

步骤

  1. 建立超级源点ss与汇点st；
  2. 像普通网络流一样建图，但其中边的上界为c-b（上界-下界）；
  3. 计算所有点的Dif（流入下界之和 - 流出下界之和）。 如果Dif[u]大于0，建立ss到u的上界为Dif的附加边； 如果Dif[u]小于0，建立u到st的上界为-Dif的附加边；
  4. 计算从ss到st的最大流；
  5. 计算每条附加边的流量。若每条附加边u的流量均为Dif[u]（即每条附加边都满载），则说明找到了可行流。

算竞训练指南上说还要建立一条st到ss的流量上界INF的边，翻了很多资料博客，其实应该不可以添加。应该是书上错了？

模板题

SGU194 - Reactor Cooling 

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//上下界网络流
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#define INF 0x7FFFFFFF
#define Maxn 22222
using namespace std;

struct Edge {
	int c, f,id;
	unsigned v, flip;
	Edge(unsigned v, int c, int f, unsigned flip,int id) :v(v), c(c), f(f), flip(flip),id(id) {}
};

class Dinic {
public:
	bool b[Maxn];
	int a[Maxn];
	unsigned p[Maxn], cur[Maxn], d[Maxn];
	vector<Edge> G[Maxn];

	unsigned s, t;
	void Init(unsigned n) {
		for (int i = 0; i <= n; ++i)
			G[i].clear();
	}
	void AddEdge(unsigned u, unsigned v, int c,int id) {
		G[u].push_back(Edge(v, c, 0, G[v].size(),id));
		G[v].push_back(Edge(u, 0, 0, G[u].size() - 1,0)); // 使用无向图时将0改为c即可
	}
	bool BFS() {
		unsigned u, v;
		queue<unsigned> q;
		memset(b, 0, sizeof(b));
		q.push(s);
		d[s] = 0;
		b[s] = 1;
		while (!q.empty()) {
			u = q.front();
			q.pop();
			for (auto it = G[u].begin(); it != G[u].end(); ++it) {
				Edge &e = *it;
				if (!b[e.v] && e.c>e.f) {
					b[e.v] = 1;
					d[e.v] = d[u] + 1;
					q.push(e.v);
				}
			}
		}
		return b[t];
	}
	int DFS(unsigned u, int a) {
		if (u == t || a == 0)
			return a;
		int flow = 0, f;
		for (unsigned &i = cur[u]; i<G[u].size(); ++i) {
			Edge &e = G[u][i];
			if (d[u] + 1 == d[e.v] && (f = DFS(e.v, min(a, e.c - e.f)))>0) {
				a -= f;
				e.f += f;
				G[e.v][e.flip].f -= f;
				flow += f;
				if (!a) break;
			}
		}
		return flow;
	}
	int MaxFlow(unsigned s, unsigned t) {
		int flow = 0;
		this->s = s;
		this->t = t;
		while (BFS()) {
			memset(cur, 0, sizeof(cur));
			flow += DFS(s, INF);
		}
		return flow;
	}
};

int Flow[1000000];
int N, M;
int Dif[Maxn];

int main() {
	ios::sync_with_stdio(false);
	while (cin >> N >> M) {
		const int ss = N + 1, st = N + 2;
		memset(Dif, 0, sizeof(Dif));
		memset(Flow, 0, sizeof(Flow));
		Dinic Din;
		Din.Init(N);
		int u, v, b, c;
		for (int i = 1; i <= M; ++i) {
			cin >> u >> v >> b >> c;
			Din.AddEdge(u, v, c - b,i);
			Dif[u] -= b;
			Dif[v] += b;
			Flow[i] = b;
		}
		for (int i = 1; i <= N; ++i) {
			if (Dif[i] > 0) Din.AddEdge(ss, i, Dif[i],0);
			if (Dif[i] < 0) Din.AddEdge(i, st, -Dif[i],0);
		}
		Din.MaxFlow(ss, st);
		bool flg = false;
		for (const auto &e : Din.G[ss]) {
			if (e.f != e.c) {
				flg = true;
				break;
			}
		}
		if (flg) cout << "NO\n";
		else {
			cout << "YES\n";
			for (int i = 1; i <= M;++i) for (const auto &e : Din.G[i]) {
				if (e.id) Flow[e.id] += e.f;
			}
			for (int i = 1; i <= M; ++i) cout << Flow[i] << '\n';
		}
	}
	return 0;
}

有源汇有上下界最大流

步骤

  1. 从t到s连一条流量下界为0，上界INF的边，将其转换为无源汇有上下界的最大流；
  2. 按照无源汇有上下界可行流的做法找出可行流（保证了每条边的流量大于下界）；
  3. 在2的基础上删除超级源汇点ss、st与附加边（名义上说是要先删除ss、st，但实际上，此时每条附加边已经满流，在运行s-t的最大流时，ss与st的流量不会再变化，所以其实不用做任何操作），从s到t再次寻找一次最大流。（可以直接在上面的建图中运行，然后给每条边加上对应b）。

模板题

在 \[ 大大大大大大\\ 大大大大大大\\ 大大大大大大\\ 大 \] 期间各大学校的OJ都挂了。。。以后更新吧。

有源汇有上下界最小流

步骤

  1. 按照无源汇有上下界的最大流的做法找出可行流（但不要建立t->s）；
  2. 添加t->s，流量上界INF；
  3. 再次运行最大流，找出ss->st可行流；
  4. 若ss不满载，则无可行流。反之，最小流为t->s的流量，每条边的流量为逆向边的流量（加上下界b）。

模板题

HDU3157 - Crazy Circuits 

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
const int Maxn = 100;
int N, M, S, T, SS, ST;
int Dif[Maxn];

bool QIn(int &x) {
	char c;
	while ((c = getchar()) != EOF && (!isdigit(c) && (c != '+'&&c != '-')));
	switch (c) {
	case '+':x = S; return true;
	case '-':x = T; return true;
	case EOF: return false;
	}
	x = 0;
	do {
		x *= 10;
		x += c - '0';
	} while ((c = getchar()) != EOF&&isdigit(c));
	return true;
}

struct Edge {
	int c, f;
	unsigned v, flip;
	Edge(unsigned v, int c, int f, unsigned flip) :v(v), c(c), f(f), flip(flip) {}
};

class Dinic {
private:
	bool b[Maxn];
	int a[Maxn];
	unsigned p[Maxn], cur[Maxn], d[Maxn];

public:
	vector<Edge> G[Maxn];
	unsigned s, t;
	void Init(unsigned n) {
		for (int i = 0; i <= n; ++i)
			G[i].clear();
	}

	void AddEdge(unsigned u, unsigned v, int c) {
		G[u].push_back(Edge(v, c, 0, G[v].size()));
		G[v].push_back(Edge(u, 0, 0, G[u].size() - 1));	//使用无向图时将0改为c即可 
	}

	bool BFS() {
		unsigned u, v;
		queue<unsigned> q;
		memset(b, 0, sizeof(b));
		q.push(s);
		d[s] = 0;
		b[s] = 1;
		while (!q.empty()) {
			u = q.front();
			q.pop();
			for (auto it = G[u].begin(); it != G[u].end(); ++it) {
				Edge &e = *it;
				if (!b[e.v] && e.c>e.f) {
					b[e.v] = 1;
					d[e.v] = d[u] + 1;
					q.push(e.v);
				}
			}
		}
		return b[t];
	}

	int DFS(unsigned u, int a) {
		if (u == t || a == 0)
			return a;
		int flow = 0, f;
		for (unsigned &i = cur[u]; i<G[u].size(); ++i) {
			Edge &e = G[u][i];
			if (d[u] + 1 == d[e.v] && (f = DFS(e.v, min(a, e.c - e.f)))>0) {
				a -= f;
				e.f += f;
				G[e.v][e.flip].f -= f;
				flow += f;
				if (!a) break;
			}
		}
		return flow;
	}

	int MaxFlow(unsigned s, unsigned t) {
		int flow = 0;
		this->s = s;
		this->t = t;
		while (BFS()) {
			memset(cur, 0, sizeof(cur));
			flow += DFS(s, INF);
		}
		return flow;
	}
};

void Input(Dinic &d) {
	memset(Dif, 0, sizeof(Dif));
	int u, v, b;
	char c;
	for (int i = 1; i <= M; ++i) {
		QIn(u);
		QIn(v);
		QIn(b);
		d.AddEdge(u, v, INF); //由于无上界，直接写INF好了，反正流量不可能达到INF-b
		Dif[u] -= b;
		Dif[v] += b;
	}
}

int main() {
	while (~scanf("%d %d",&N,&M) && M) { //N可以等于0！
		S = N + 1, T = N + 2;
		SS = S + 2, ST = T + 2;
		Dinic D;
		Input(D);
		int sum = 0;
		for (int i = 1; i <= T; ++i) { //建立与超级源汇点ss、st的边（别漏了源汇点！）
			if (Dif[i] > 0) {
				D.AddEdge(SS, i, Dif[i]);
				sum += Dif[i];
			}
			if (Dif[i] < 0) D.AddEdge(i, ST, -Dif[i]);
		}
		int ans=D.MaxFlow(SS, ST);
		D.AddEdge(T, S, INF);
		ans += D.MaxFlow(SS, ST);
		if (ans != sum) {
			puts("impossible");
		}
		else {
			printf("%d\n", D.G[T].rbegin()->f);
		}
	}
	return 0;
}