题目地址:
https://www.acwing.com/problem/content/2190/
给定一个包含 n n n个点 m m m条边的有向图,每条边都有一个流量下界和流量上界。求一种可行方案使得在所有点满足流量平衡条件的前提下,所有边满足流量限制。
输入格式:
第一行包含两个整数
n
n
n和
m
m
m。接下来
m
m
m行,每行包含四个整数
a
,
b
,
c
,
d
a,b,c,d
a,b,c,d表示点
a
a
a和
b
b
b之间存在一条有向边,该边的流量下界为
c
c
c,流量上界为
d
d
d。点编号从
1
1
1到
n
n
n。
输出格式:
如果存在可行方案,则第一行输出YES
,接下来
m
m
m行,每行输出一个整数,其中第
i
i
i行的整数表示输入的第
i
i
i条边的流量。如果不存在可行方案,直接输出一行NO
。如果可行方案不唯一,则输出任意一种方案即可。
数据范围:
1
≤
n
≤
200
1≤n≤200
1≤n≤200
1
≤
m
≤
10200
1≤m≤10200
1≤m≤10200
1
≤
a
,
b
≤
n
1≤a,b≤n
1≤a,b≤n
0
≤
c
≤
d
≤
10000
0≤c≤d≤10000
0≤c≤d≤10000
无源汇上下界可行流又称为循环流,像是一定量的水在水管里循环流动。由于每条边有容量下限,所以容易想到构建新的网络,将每条边的容量设为是原图的容量上下限之差,这样在新网络里任一一个可行流必然满足容量限制,但是流量守恒就不一定满足了,我们可以采用这样的方法,如果入边的总容量下限 c c c大于出边的总容量下限 c ′ c' c′,那么可以从源点补充差值给这个点(即从源点到这个点开一条容量是 c − c ′ c-c' c−c′的边);反之,则从该点把多出来的差补给汇点(即从该点到汇点开一条容量是 c ′ − c c'-c c′−c的边)。题目问是否存在满足容量限制的可行流,相当于问新网络里的最大流是否可以达到源点的出边容量之和。可以粗略的看一下对应关系,对于新网络里的任意一个满流,去掉源点和汇点(和它们连接的边)之后,将每个边里的流加一下其在原图里的下限,就得到的一个原图的可行流;对于原图的一个可行流,将每个边里的流减去其在原图里的下限,再加上源点和汇点按上述所说方式构图,就能得到新网络里的一个满流。所以问题就转化为在新网络里求最大流,可以用Dinic算法。代码如下:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, M = (10200 + N) * 2, INF = 1e8;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], l[M], idx;
int q[N], d[N], cur[N], diff[N];
// 构造新网络的残留网络。每条边的容量是上限 - 下限
void add(int a, int b, int c, int d) {
e[idx] = b, ne[idx] = h[a], f[idx] = d - c, l[idx] = c, h[a] = idx++;
e[idx] = a, ne[idx] = h[b], f[idx] = 0, h[b] = idx++;
}
bool bfs() {
memset(d, -1, sizeof d);
int hh = 0, tt = 0;
q[tt++] = S, d[S] = 0, cur[S] = h[S];
while (hh < tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int v = e[i];
if (d[v] == -1 && f[i]) {
d[v] = d[t] + 1;
if (v == T) return true;
cur[v] = h[v];
q[tt++] = v;
}
}
}
return false;
}
int dfs(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
cur[u] = i;
int v = e[i];
if (d[v] == d[u] + 1 && f[i]) {
int t = dfs(v, min(limit - flow, f[i]));
if (!t) d[v] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while(flow = dfs(S, INF)) r += flow;
return r;
}
int main() {
cin >> n >> m;
S = 0, T = n + 1;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, c, d);
diff[a] -= c, diff[b] += c;
}
int tot = 0;
// 求一下满流的流量
for (int i = 1; i <= n; i++)
if (diff[i] > 0) add(S, i, 0, diff[i]), tot += diff[i];
else if (diff[i] < 0) add(i, T, 0, -diff[i]);
// 如果最大流不是源点出边全满的流,则说明无解,否则输出流量
if (dinic() < tot) cout << "NO" << endl;
else {
cout << "YES" << endl;
for (int i = 0; i < m * 2; i += 2)
// 流量是残留网络的反向边的容量,再加上下限
cout << f[i ^ 1] + l[i] << endl;
}
return 0;
}
时间复杂度 O ( n 2 m ) O(n^2m) O(n2m),空间 O ( n ) O(n) O(n)。