无源汇上下界可行流
模型描述
在流网络中，每条边的流量范围不再是([0, c_i])，而是([down_i, up_i])，同时还要满足流量守恒。求一个可行流。
建模
我们要想办法转变为一般的最大流问题。
考虑将容量上界和下界分别减去(down_i)，即可行流需满足(0 leq f'_i leq up_i - down_i)，即(down_i leq f'_i + down_i leq up_i)。
若最后存在可行流，那么流量为(f'_i + down_i)。问题就转化成了在一般的流网络上求(f'_i)的问题了。
但是，在转化成一般的网络流问题的过程中，会出现流量不守恒的情况。
原因是对于节点(i)，将指向(i)的边集设为(In_i)，将(i)指向其他节点的边集记为(Out_i)。有(sum_{j in In_i} f_j = sum_{j in Out_i} f_j)，但是不一定满足(sum_{j in In_i} f_j + down_j = sum_{j in Out_i} f_j + down_j)。
因此我们需要将流网络进行一定调整，设置源点(S)、汇点(T)，记每条边(alpha(i) = sum_{j in Out_i} down_j - sum_{j in In_i} down_j)。
如果(alpha(i) > 0)，则从(S)向(i)连一条容量是(alpha(i))的边；如果(alpha(i) < 0)，则从(i)向(T)连一条容量是(-alpha(i))的边。
跑一遍最大流，如果最大流小于以(S)为起点的边的容量和，那么说明肯定会有流量不守恒的情况，因此 不存在可行流。反之，存在可行流。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 210, M = (N + 10200) * 2, inf = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], l[M], ne[M], idx;
int cur[N], d[N], ad[N];
void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = d - c, l[idx] = c, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}
bool bfs()
{
memset(d, -1, sizeof(d));
queue<int> que;
que.push(S);
d[S] = 0, cur[S] = h[S];
while(que.size()) {
int t = que.front();
que.pop();
for(int i = h[t]; ~i; i = ne[i]) {
int ver = e[i];
if(d[ver] == -1 && f[i]) {
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if(ver == T) return true;
que.push(ver);
}
}
}
return false;
}
int find(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 ver = e[i];
if(d[ver] == d[u] + 1 && f[i]) {
int t = find(ver, min(f[i], limit - flow));
if(!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
int res = 0, flow;
while(bfs()) {
while(flow = find(S, inf)) {
res += flow;
}
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof(h));
S = 0, T = n + 1;
for(int i = 0; i < m; i ++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
ad[a] -= c, ad[b] += c;
}
int tot = 0;
for(int i = 1; i <= n; i ++) {
if(ad[i] > 0) add(S, i, 0, ad[i]), tot += ad[i];
else add(i, T, 0, -ad[i]);
}
if(dinic() != tot) puts("NO");
else {
puts("YES");
for(int i = 0; i < m * 2; i += 2) {
printf("%d
", f[i ^ 1] + l[i]);
}
}
return 0;
}
有源汇上下界可行流/最大流
模型描述
在无源汇上下界可行流问题的流网络基础上，指定了源点和汇点。求可行流/最大流。
建模
从汇点(t)向源点(s)连一条上界是(infty)，下界是(0)的边。其他步骤同无源汇情形。
以源点为(S)，汇点为(T)，求得一个可行流的流量(f_1)为(t)到(s)的边的反向边。
若求最大流，那么删掉(t)到(s)的边及其反向边，以(s)为源点，(t)为汇点，再跑一遍最大流，流量记为(f_2)
最终结果为(f = f_1 + f_2)
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 210, M = (N + 10000) * 2, inf = 1e8;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], l[M], idx;
int cur[N], d[N], A[N];
void add(int a, int b, int c, int d)
{
e[idx] = b, f[idx] = d - c, l[idx] = c, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}
bool bfs()
{
memset(d, -1, sizeof(d));
queue<int> que;
que.push(S);
d[S] = 0, cur[S] = h[S];
while(que.size()) {
int t = que.front();
que.pop();
for(int i = h[t]; ~i; i = ne[i]) {
int ver = e[i];
if(d[ver] == -1 && f[i]) {
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if(ver == T) return true;
que.push(ver);
}
}
}
return false;
}
int find(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 ver = e[i];
if(d[ver] == d[u] + 1 && f[i]) {
int t = find(ver, min(f[i], limit - flow));
if(!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
int res = 0, flow;
while(bfs()) {
while(flow = find(S, inf)) {
res += flow;
}
}
return res;
}
int main()
{
int s, t;
scanf("%d%d%d%d", &n, &m, &s, &t);
memset(h, -1, sizeof(h));
S = 0, T = n + 1;
for(int i = 0; i < m; i ++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
A[a] -= c, A[b] += 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]);
}
add(t, s, 0, inf);
if(tot != dinic()) puts("No Solution");
else {
int res = f[idx - 1];
f[idx - 1] = f[idx - 2] = 0;
S = s, T = t;
printf("%d
", res + dinic());
}
return 0;
}
有源汇上下界最小流
建模
在可行流的基础上，以(t)为源点，(s)为汇点，求最大流，记为(f_2)
最终结果为(f = f_1 - f_2)
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 50010, M = (N + 125010) * 2, inf = 2147483647;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], l[M], idx;
int cur[N], d[N], A[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));
queue<int> que;
que.push(S);
d[S] = 0, cur[S] = h[S];
while(que.size()) {
int t = que.front();
que.pop();
for(int i = h[t]; ~i; i = ne[i]) {
int ver = e[i];
if(d[ver] == -1 && f[i]) {
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if(ver == T) return true;
que.push(ver);
}
}
}
return false;
}
int find(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 ver = e[i];
if(d[ver] == d[u] + 1 && f[i]) {
int t = find(ver, min(f[i], limit - flow));
if(!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
int res = 0, flow;
while(bfs()) {
while(flow = find(S, inf)) {
res += flow;
}
}
return res;
}
int main()
{
int t, s;
scanf("%d%d%d%d", &n, &m, &s, &t);
memset(h, -1, sizeof(h));
S = 0, T = n + 1;
for(int i = 0; i < m; i ++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
add(a, b, c, d);
A[a] -= c, A[b] += 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]);
}
add(t, s, 0, inf);
if(tot != dinic()) puts("No Solution");
else {
int res = f[idx - 1];
f[idx - 1] = f[idx - 2] = 0;
S = t, T = s;
printf("%d
", res - dinic());
}
return 0;
}