把网络流24题刷完我就算萌新了。
(持续更新直到刷完为止)
\(1.\)洛谷P2756 飞行员配对方案问题
题意：派出最多架的飞机，并且每架飞机上都是一个英国飞行员和外籍飞行员
分析：经典的二分图匹配问题，将英国飞行员当做二分图的左部，外籍飞行员当做二分图的右部。可以用匈牙利算法求解，但这里使用网络流(最大流)。
考虑如何建图：
设立一个源点\(st\)，一个汇点\(ed\)。
\(I.\)让源点\(st\)向二分图的左部建一条流量为\(1\)的边，
\(II.\)让二分图的右部向汇点\(ed\)建一条流量为\(1\)的边，
\(III.\)如果英国飞行员\(u\)可以和外籍飞行员\(v\)配合，那么\(u\)和\(v\)建一条流量为\(1\)的边。
最后跑一遍最大流即可得到最大匹配数。
如何输出配对方案：
遍历所有的英国飞行员所连的边，如果此边\((u,v)\)流量不是\(1\)而是\(0\)说明\((u,v)\)配对。注意源点向英国飞行员所连的边流量会为0，但此时不应输出。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
const int maxn = 300 + 5;
const int inf = 0x3f3f3f3f;
int n, m, u, v, st, ed, cnt, ans, head[maxn];
int flag, maxflow, vis[maxn], cur[maxn], deep[maxn];
struct Graph {
int v, w, next;
} edge[2 * maxn * maxn];
void addedge(int u, int v, int w) {
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int bfs(int st, int ed) {
for (int i = 0; i <= n + m + 5; i++) vis[i] = 0, cur[i] = head[i], deep[i] = inf;
queue<int> q;
q.push(st);
deep[st] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].v;
if (deep[v] > deep[u] + 1 && edge[i].w) {
deep[v] = deep[u] + 1;
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return deep[ed] != inf;
}
int dfs(int u, int ed, int flow) {
if (u == ed) {
flag = 1;
maxflow += flow;
return flow;
}
int now = 0, used = 0;
for (int i = cur[u]; ~i; i = edge[i].next) {
int v = edge[i].v;
cur[u] = i;
if (deep[v] == deep[u] + 1 && edge[i].w) {
if (now = dfs(v, ed, min(flow - used, edge[i].w))) {
used += now;
edge[i].w -= now;
edge[i ^ 1].w += now;
if (used == flow) break;
}
}
}
return used;
}
int dinic(int st, int ed) {
while (bfs(st, ed)) {
flag = 1;
while (flag) flag = 0, dfs(st, ed, inf);
}
return maxflow;
}
int main() {
memset(head, -1, sizeof head);
scanf("%d %d", &n, &m);
st = 0, ed = m + 1;
while (~scanf("%d %d", &u, &v)) {
if (u == -1 && v == -1) break;
addedge(u, v, 1), addedge(v, u, 0);
}
for (int i = 1; i <= n; i++) addedge(st, i, 1), addedge(i, st, 0);
for (int i = n + 1; i <= m; i++) addedge(i, ed, 1), addedge(ed, i, 0);
ans = dinic(st, ed);
if (!ans) return 0 * puts("No Solution!");
printf("%d\n", ans);
for (int i = 1; i <= n; i++) {
for (int j = head[i]; ~j; j = edge[j].next) {
if (edge[j].v != st && edge[j].w == 0 && edge[j ^ 1].w == 1)
printf("%d %d\n", i, edge[j].v);
}
}
return 0;
}\(2.\)洛谷P2764 最小路径覆盖问题
做这道题首先我们要知道一个关于二分图的公式，
最小路径覆盖数 = 图的顶点数 - 图相应的二分图的最大匹配数
图转化为相应的二分图：对每个点拆点，拆成入点\(x_1\)(\(i\))和出点\(x_2\)(\(i+n\))，将这些入点作为二分图的左部，出点作为二分图的右部。
像\(1\)中一样建立源点与汇点，源点与左部相连，右部与汇点相连。
对于边(\(u,v\))，我们将\(u\)连向\(v+n\)即可。
跑一遍最大流，得到最大匹配数，则最小路径覆盖数就得到了。
如何输出路径：遍历所有的边(\(u,v\))(正向边即可)，如果这条边的流量为\(0\)，说明这条边一定在某条路径上。我们用非路径压缩的并查集来维护这些关系，如果此边流量为\(0\)，则将\(v\)并向\(u\)。那么最后一定有祖先为自己的点，\(dfs\)这些点即可。判断边的时候要注意源点的影响，
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
const int maxn = 300 + 5;
const int maxm = 12000 + 5;
const int inf = 0x3f3f3f3f;
int n, m, cnt, pre[maxn], head[maxn];
int u, v, st, ed, flag, maxflow, deep[maxn], vis[maxn], cur[maxn];
struct Graph {
int u, v, w, next;
} edge[maxm << 1];
void addedge(int u, int v, int w) {
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int bfs(int st, int ed) {
for (int i = 0; i <= n + n + 5; i++) deep[i] = inf, vis[i] = 0, cur[i] = head[i];
queue<int> q;
q.push(st);
deep[st] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].v, w = edge[i].w;
if (w && deep[v] > deep[u] + 1) {
deep[v] = deep[u] + 1;
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return deep[ed] != inf;
}
int dfs(int u, int ed, int flow) {
if (u == ed) {
flag = 1;
maxflow += flow;
return flow;
}
int now = 0, used = 0;
for (int i = cur[u]; ~i; i = edge[i].next) {
cur[u] = i;
int v = edge[i].v;
if (edge[i].w && deep[v] == deep[u] + 1) {
now = dfs(v, ed, min(flow - used, edge[i].w));
if (!now) continue;
edge[i].w -= now;
edge[i ^ 1].w += now;
used += now;
if (used == flow) break;
}
}
return used;
}
void dinic(int st, int ed) {
while (bfs(st, ed)) {
flag = 1;
while (flag) {
flag = 0;
dfs(st, ed, inf);
}
}
}
void dfs(int x) {
printf("%d ", x);
vis[x] = 1;
for (int i = head[x]; ~i; i = edge[i].next) {
if (!vis[edge[i].v] && edge[i].w == 0 && edge[i].v > n) {
dfs(edge[i].v - n);
}
}
}
int main() {
scanf("%d %d", &n, &m);
memset(head, -1, sizeof head);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &u, &v);
addedge(u, v + n, 1), addedge(v + n, u, 0);
}
st = 0, ed = n + n + 1;
for (int i = 1; i <= n; i++) addedge(st, i, 1), addedge(i, st, 0);
for (int i = n + 1; i <= n + n; i++) addedge(i, ed, 1), addedge(ed, i, 0);
dinic(st, ed);
for (int i = 1; i <= n; i++) pre[i] = i;
for (int j = 0; j <= cnt; j++) {
if (edge[j].u >= 1 && edge[j].u <= n && edge[j].v > n && edge[j].v <= n + n && edge[j].w == 0) {
// if (pre[edge[j].v - n] != pre[edge[j].u])
pre[edge[j].v - n] = pre[edge[j].u];
}
}
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; i++) {
if (pre[i] == i) {
dfs(i);
puts("");
}
}
printf("%d\n", n - maxflow);
return 0;
}\(3.\)洛谷P2765 魔术球问题
分析：因为柱子数是固定不变的，我们可以将\(n\)根柱子理解为\(n\)条路径。那么问题就可以转化为不断向路径中加入数，直到加入某个数使得路径数\(>\)\(n\)。从\(1\)开始枚举直到不满足条件。
如何建图：
每次新枚举一个数\(x\)，那么它有可能是一个柱子的开头，所以我们从源点向\(x\)建一条流量为\(1\)的边，它也有可能是某个柱子的最后一个数，所以\(x\)向汇点连一条流量为\(1\)的边。然后现在就是考虑数和数之间的边，题目限制\(x\)只有和相邻数相加为完全平方数时才能放入，所以枚举\(y\)\(\in\)\([1,x-1]\)，如果\(y\)能与\(x\)形成完全平方数就和\(x\)建边(\(x\)作为右部)。
然后在残余网络上跑最大流得到每次的最大匹配数，每次让总顶点数减去其再判断即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
const int maxn = 7000 + 5;
const int maxm = 100 + 5;
const int inf = 0x3f3f3f3f;
int n, cnt, head[maxn];
int st, ed, ans, now, maxf, flag, deep[maxn], vis[maxn], cur[maxn], path[maxn];
struct Graph {
int v, w, next;
} edge[200000];
void addedge(int u, int v, int w) {
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int bfs(int st, int ed) {
for (int i = 0; i <= ed; i++) deep[i] = inf, vis[i] = 0, cur[i] = head[i];
queue<int> q;
q.push(st);
deep[st] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].v;
if (edge[i].w && deep[v] > deep[u] + 1) {
deep[v] = deep[u] + 1;
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return deep[ed] != inf;
}
int dfs(int u, int ed, int flow) {
if (u == ed) {
flag = 1;
maxf += flow;
return flow;
}
int now = 0, used = 0;
for (int i = cur[u]; ~i; i = edge[i].next) {
int v = edge[i].v;
cur[u] = i;
if (edge[i].w && deep[v] == deep[u] + 1) {
now = dfs(v, ed, min(flow - used, edge[i].w));
if (!now) continue;
edge[i].w -= now;
edge[i ^ 1].w += now;
used += now;
if (used == flow) break;
}
}
return used;
}
void dinic(int st, int ed) {
while (bfs(st, ed)) {
flag = 1;
while (flag) {
flag = 0;
dfs(st, ed, inf);
}
}
}
int main() {
scanf("%d", &n);
memset(head, -1, sizeof head);
st = 0, ed = 5001;
while (true) {
ans++, now++;
addedge(st, now, 1), addedge(now, st, 0);
for (int i = 1; i <= now - 1; i++) {
if (sqrt(i + now) == (int)(sqrt(i + now)))
addedge(i, now + 2000, 1), addedge(now + 2000, i, 0);
}
addedge(now + 2000, ed, 1), addedge(ed, now + 2000, 0);
maxf = 0, dinic(st, ed);
ans -= maxf;
if (ans > n) break;
}
printf("%d\n", now - 1);
for (int i = 1; i <= now - 1; i++) {
for (int j = head[i]; ~j; j = edge[j].next) {
if (!edge[j].w) {
path[i] = edge[j].v - 2000;
break;
}
}
}
memset(vis, 0, sizeof vis);
for (int i = 1; i <= now - 1; i++) {
if (vis[i]) continue;
int temp = i;
while (temp != -2000) {
vis[temp] = 1;
printf("%d ", temp);
temp = path[temp];
}
puts("");
}
return 0;
}\(4.\)洛谷P2763 试题库问题
分析：
二分匹配，只不过左部可以匹配多个右部。
让题的类型\(x\in[1,n]\)作为二分图的左部，让题\(y\in[n+1,n+1+m]\)作为二分图的右部。
源点向题的类型建流量为题类型所需题数的边，题向汇点建流量为\(1\)的边(题只能用在某个类型一次)，题的类型与题建流量为\(1\)的边。跑一遍最大流即可。
输出方案：枚举题的类型所连的边，判断流量是否为\(0\)即是否匹配上即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
const int maxn = 20000 + 5;
const int maxm = 100 + 5;
const int inf = 0x3f3f3f3f;
int k, n, m, x, y;
int st, ed, cnt, head[maxn];
int maxf, flag, deep[maxn], cur[maxn], vis[maxn];
struct Graph {
int v, w, next;
} edge[maxn << 1];
void addedge(int u, int v, int w) {
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int bfs(int st, int ed) {
for (int i = 0; i <= ed; i++) vis[i] = 0, deep[i] = inf, cur[i] = head[i];
queue<int> q;
q.push(st);
deep[st] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].v;
if (edge[i].w && deep[v] > deep[u] + 1) {
deep[v] = deep[u] + 1;
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return deep[ed] != inf;
}
int dfs(int u, int ed, int flow) {
if (u == ed) {
flag = 1;
maxf += flow;
return flow;
}
int now = 0, used = 0;
for (int i = cur[u]; ~i; i = edge[i].next) {
cur[u] = head[i];
int v = edge[i].v;
if (edge[i].w && deep[v] == deep[u] + 1) {
now = dfs(v, ed, min(flow - used, edge[i].w));
if (!now) continue;
edge[i].w -= now;
edge[i ^ 1].w += now;
used += now;
if (used == flow) break;
}
}
return used;
}
void dinic(int st, int ed) {
while (bfs(st, ed)) {
flag = 1;
while (flag) {
flag = 0;
dfs(st, ed, inf);
}
}
}
int main() {
memset(head, -1, sizeof head);
scanf("%d %d", &k, &n);
st = 0, ed = 20002;
for (int i = 1; i <= k; i++) {
scanf("%d", &x);
addedge(st, i, x), addedge(i, st, 0);
m += x;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
for (int j = 1; j <= x; j++) {
scanf("%d", &y);
addedge(y, i + k, 1), addedge(i + k, y, 0);
}
addedge(i + k, ed, 1), addedge(ed, i + k, 0);
}
dinic(st, ed);
for (int i = 1; i <= k; i++) {
printf("%d: ", i);
for (int j = head[i]; ~j; j = edge[j].next) {
if (edge[j].w == 0 && edge[j].v != st) printf("%d ", edge[j].v - k);
}
puts("");
}
return 0;
}
原文：https://www.cnblogs.com/ChaseNo1/p/11503970.html