题目描述
有上下界的网络流问题总结
1.无源汇上下界可行流
2.有源汇上下界可行流
3.有源汇上下界最大流
4.有源汇上下界最小流
1.无源汇上下界可行流
step1：建立新图G’。新边容量为d-c（上界-下界）
s = 0, t = n+1;
for (int i = 0; i < m; i ++ )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, c, d);
A[b] += c, A[a] -= c;
}
step2：建立虚拟源点汇点。流入大于流出点，连s到i，容量为A[i]；流出小于流入点，连i到t，容量为-A[i]
int tot = 0;
for (int i = 1; i <= n; i ++ )
if (A[i] > 0) add(s, i, 0, A[i]), tot += A[i];
else if (A[i] < 0) add(i, t, 0, -A[i]);
step3：判断流量守恒条件dinic() == tot。所有附加边的最大流满流，说明原图存在可行流（证明不会qaq）
if (tot != dinic()) puts("NO");
step4: 输出原图可行流
else
{
puts("YES");
for (int i = 0; i < m*2; i += 2)
cout << f[i^1] + l[i] << endl;
}
时间复杂度
dinic算法 O(n^2 * m);
C++ 代码
s = 0, t = n+1;
for (int i = 0; i < m; i ++ )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, c, d);
A[b] += c, A[a] -= c;
}
int tot = 0;
for (int i = 1; i <= n; i ++ )
if (A[i] > 0) add(s, i, 0, A[i]), tot += A[i];
else if (A[i] < 0) add(i, t, 0, -A[i]);
if (tot != dinic()) puts("NO");
else
{
puts("YES");
for (int i = 0; i < m*2; i += 2)
cout << f[i^1] + l[i] << endl;
}
2.有源汇上下界可行流
step0：从真正的源点S汇点T连一条上界为∞，下界为0的边，原问题转化为1（证明不会）
add(T, S, INF);
step1：建立新图G’。新边容量为d-c（上界-下界）
s = 0, t = n+1;
for (int i = 0; i < m; i ++ )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, c, d);
A[b] += c, A[a] -= c;
}
step2：流入大于流出点，连s到i，容量为A[i]；流出小于流入点，连i到t，容量为-A[i]
int tot = 0;
for (int i = 1; i <= n; i ++ )
if (A[i] > 0) add(s, i, 0, A[i]), tot += A[i];
else if (A[i] < 0) add(i, t, 0, -A[i]);
step3：判断流量守恒条件dinic() == tot。所有附加边的最大流满流，说明原图存在可行流（证明不会qaq）
if (tot != dinic()) puts("NO");
原图答案 = 新图满流可行流 + 原图残余网络可行流（最大或最小）
3.有源汇上下界最大流
step0：从真正的源点S汇点T连一条上界为∞，下界为0的边
add(T, S, INF);
step1：建立新图G’。新边容量为d-c（上界-下界）
s = 0, t = n+1;
for (int i = 0; i < m; i ++ )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, c, d);
A[b] += c, A[a] -= c;
}
step2：流入大于流出点，连s到i，容量为A[i]；流出小于流入点，连i到t，容量为-A[i]
int tot = 0;
for (int i = 1; i <= n; i ++ )
if (A[i] > 0) add(s, i, 0, A[i]), tot += A[i];
else if (A[i] < 0) add(i, t, 0, -A[i]);
step3：在新图上找可行流，找不到就结束 dinic() < tot
if (dinic() < tot) puts("No Solution");
step4: 删掉虚拟源点和汇点，删掉T到S的无穷边。
int res = f[idx-1];
s = S, t = T;
f[idx-1] = f[idx-2] = 0;
step5：在原图中的残余网络中找最大流，答案为新图满流可行流+原图残余网络最大流（证明不会）
cout << dinic() + res << endl;
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> S >> T;
s = 0, t = n+1;
while (m -- )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, d-c);
A[a] -= c, A[b] += c;
}
int tot = 0;
for (int i = 1; i <= n; i ++ )
if (A[i] > 0) add(s, i, A[i]), tot += A[i];
else if (A[i] < 0) add(i, t, -A[i]);
add(T, S, INF);
if (dinic() < tot) puts("No Solution");
else
{
int res = f[idx-1];
s = S, t = T;
f[idx-1] = f[idx-2] = 0;
cout << dinic() + res << endl;
}
return 0;
}
4.有源汇上下界最小流
step0：从真正的源点S汇点T连一条上界为∞，下界为0的边
add(T, S, INF);
step1：建立新图G’。新边容量为d-c（上界-下界）
s = 0, t = n+1;
for (int i = 0; i < m; i ++ )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, c, d);
A[b] += c, A[a] -= c;
}
step2：流入大于流出点，连s到i，容量为A[i]；流出小于流入点，连i到t，容量为-A[i]
int tot = 0;
for (int i = 1; i <= n; i ++ )
if (A[i] > 0) add(s, i, 0, A[i]), tot += A[i];
else if (A[i] < 0) add(i, t, 0, -A[i]);
step3：在新图上找可行流，找不到就结束 dinic() < tot
if (dinic() < tot) puts("No Solution");
step4: 删掉虚拟源点和汇点，删掉T到S的无穷边。
int res = f[idx-1];
s = T, t = S;
f[idx-1] = f[idx-2] = 0;
step5：在原图中的残余网络中找最大流，答案为新图满流可行流-原图残余网络最大流（S->T最小 等价 T->S最大）
cout << res - dinic() << endl;
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m >> S >> T;
s = 0, t = n+1;
while (m -- )
{
int a, b, c, d;
cin >> a >> b >> c >> d;
add(a, b, d-c);
A[a] -= c, A[b] += c;
}
int tot = 0;
for (int i = 1; i <= n; i ++ )
if (A[i] > 0) add(s, i, A[i]), tot += A[i];
else if (A[i] < 0) add(i, t, -A[i]);
add(T, S, INF);
if (dinic() < tot) puts("No Solution");
else
{
int res = f[idx-1];
s = T, t = S;
f[idx-1] = f[idx-2] = 0;
cout << res - dinic() << endl;
}
return 0;
}
