3.上下界流
无源汇上下界可行流
给有向图 G， 每条边都有一个流量上界和流量下界。若存在可行流，则输出每条边的流量，若不存在输出“NO“
思路：
对于每条边，先流下界，统计每个点的流量，所有点的流量和一定是0，建立一个超级源点连接所有流量为正的点，超级汇点连接流量为负的点，跑最大流，看能不能跑满流。
/*
* @Author: zhl
* @Date: 2020-10-20 11:09:59
*/
int val[N];
int minF[N];
signed main() {
scanf("%d%d", &n, &m);
memset(head, -1, sizeof(int) * (n + 10));
for (int i = 1; i <= m; i++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
addEdge(a, b, d - c);
val[a] -= c;
val[b] += c;
minF[i - 1] = c;
}
int sum = 0;
for (int i = 1; i <= n; i++) {
if (val[i] > 0)addEdge(0, i, val[i]), sum += val[i];
if (val[i] < 0)addEdge(i, n + 1, -val[i]);
}
s = 0, t = n + 1;
int maxflow = Dinic();
if (maxflow == sum) {
printf("YES
");
for (int i = 0; i < m; i++) {
printf("%d
", E[(2*i)^1].flow + minF[i]);
}
}
else {
printf("NO
");
}
}
有源汇上下界最大流
还是像无源汇上下界那样。
addEdge(t,s,inf)，这么一加，然后跑一遍超级源点到超级汇点的可行流加的这条边的反向边，就是一个
s到t的基础流然后再删掉这边，在此时的残留网络中跑一遍
s到t的最大流两个答案加起来就是 有源汇上下界最大流
/*
* @Author: zhl
* @Date: 2020-10-20 11:09:59
*/
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 1e4 + 10, M = 1e5 + 10, inf = 1e9;
int n, m, s, t, tot, head[N];
int ans, dis[N], cur[N];
struct Edge {
int to, next, flow;
}E[M << 1];
void addEdge(int from, int to, int w) {
E[tot] = Edge{ to,head[from],w };
head[from] = tot++;
E[tot] = Edge{ from,head[to],0 };
head[to] = tot++;
}
int bfs() {
for (int i = 0; i <= n + 1; i++) dis[i] = -1;
queue<int>Q;
Q.push(s);
dis[s] = 0;
cur[s] = head[s];
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = head[u]; ~i; i = E[i].next) {
int v = E[i].to;
if (E[i].flow && dis[v] == -1) {
Q.push(v);
dis[v] = dis[u] + 1;
cur[v] = head[v];
if (v == t)return 1; //分层成功
}
}
}
return 0;
}
int dfs(int x, int sum) {
if (x == t)return sum;
int k, res = 0;
for (int i = cur[x]; ~i && res < sum; i = E[i].next) {
cur[x] = i;
int v = E[i].to;
if (E[i].flow > 0 && (dis[v] == dis[x] + 1)) {
k = dfs(v, min(sum, E[i].flow));
if (k == 0) dis[v] = -1; //不可用
E[i].flow -= k; E[i ^ 1].flow += k;
res += k; sum -= k;
}
}
return res;
}
int Dinic() {
int ans = 0;
while (bfs()) {
ans += dfs(s, inf);
}
return ans;
}
int val[N];
int minF[N];
signed main() {
int S, T;
scanf("%d%d%d%d", &n, &m, &S, &T);
memset(head, -1, sizeof(int) * (n + 10));
for (int i = 1; i <= m; i++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
addEdge(a, b, d - c);
val[a] -= c;
val[b] += c;
minF[i - 1] = c;
}
int sum = 0;
for (int i = 1; i <= n; i++) {
if (val[i] > 0)addEdge(0, i, val[i]), sum += val[i];
if (val[i] < 0)addEdge(i, n + 1, -val[i]);
}
s = 0, t = n + 1;
addEdge(T, S, inf);
int maxflow = Dinic();
if (maxflow == sum) {
int base = E[tot - 1].flow;
E[tot - 1].flow = E[tot - 2].flow = 0;
s = S; t = T;
printf("%d
", base + Dinic());
}
else {
printf("No Solution
");
}
}
有源汇上下界最小流
跟上面类似，跑
t到s的最大流，减去就可以了
/*
* @Author: zhl
* @Date: 2020-10-20 11:09:59
*/
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 2e6 + 10, M = 2e6 + 10, inf = 1e9;
int n, m, s, t, tot, head[N];
int ans, dis[N], cur[N];
struct Edge {
int to, next, flow;
}E[M << 1];
void addEdge(int from, int to, int w) {
E[tot] = Edge{ to,head[from],w };
head[from] = tot++;
E[tot] = Edge{ from,head[to],0 };
head[to] = tot++;
}
int bfs() {
for (int i = 0; i <= n + 1; i++) dis[i] = -1;
queue<int>Q;
Q.push(s);
dis[s] = 0;
cur[s] = head[s];
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = head[u]; ~i; i = E[i].next) {
int v = E[i].to;
if (E[i].flow && dis[v] == -1) {
Q.push(v);
dis[v] = dis[u] + 1;
cur[v] = head[v];
if (v == t)return 1; //分层成功
}
}
}
return 0;
}
int dfs(int x, int sum) {
if (x == t)return sum;
int k, res = 0;
for (int i = cur[x]; ~i && res < sum; i = E[i].next) {
cur[x] = i;
int v = E[i].to;
if (E[i].flow > 0 && (dis[v] == dis[x] + 1)) {
k = dfs(v, min(sum, E[i].flow));
if (k == 0) dis[v] = -1; //不可用
E[i].flow -= k; E[i ^ 1].flow += k;
res += k; sum -= k;
}
}
return res;
}
int Dinic() {
int ans = 0;
while (bfs()) {
ans += dfs(s, inf);
}
return ans;
}
int val[N];
int minF[N];
signed main() {
int S, T;
scanf("%d%d%d%d", &n, &m, &S, &T);
memset(head, -1, sizeof(int) * (n + 10));
for (int i = 1; i <= m; i++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
addEdge(a, b, d - c);
val[a] -= c;
val[b] += c;
minF[i - 1] = c;
}
int sum = 0;
for (int i = 1; i <= n; i++) {
if (val[i] > 0)addEdge(0, i, val[i]), sum += val[i];
if (val[i] < 0)addEdge(i, n + 1, -val[i]);
}
s = 0, t = n + 1;
addEdge(T, S, inf);
int maxflow = Dinic();
if (maxflow == sum) {
int base = E[tot - 1].flow;
E[tot - 1].flow = E[tot - 2].flow = 0;
s = T; t = S;//只有这里改动了
printf("%d
", base - Dinic());
}
else {
printf("No Solution
");
}
}