写这篇博客，主要是为了记录一下做网络流24题中几道有价值的题目。个人感觉网络流写法并不是主要难点，难在建模和问题的转化上。
最小路径覆盖问题
二分图匹配问题。题目既然要求最少的路径覆盖，那么转化一下问题，最小的路径覆盖就是让越多的点相连通。因为是“简单路”并且是有向的，所以不难想到用二分图匹配的做法来求出最多的可以连上的边。
最后的答案就是 总点数 - 最大匹配数。二分图匹配问题可以用网络流解决。
Code:
#include <bits/stdc++.h>
//#6002. 「网络流 24 题」最小路径覆盖
#define MAXN 400 + 10
using namespace std;
const int inf = 0x3f3f3f3f;
struct edge {
int to, cap, rev;
};
vector<edge> G[MAXN];
int level[MAXN], iter[MAXN], n, e;
bool vis[MAXN];
void add_edge(int from, int to, int cap) {
G[from].push_back((edge){to, cap, G[to].size()});
G[to].push_back((edge){from, 0, G[from].size() - 1});
}
void bfs(int s) {
memset(level, -1, sizeof level);
queue<int> que;
level[s] = 0;
que.push(s);
while (!que.empty()) {
int v = que.front(); que.pop();
for (int i = 0; i < G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
int dfs(int v, int t, int f) {
if (v == t) return f;
for (int &i = iter[v]; i < G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap > 0 && level[e.to] > level[v]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
//dinic
int max_flow(int s, int t) {
int flow = 0;
for(;;) {
// printf("calculating, level[%d] = %d\n", t, level[t]);
bfs(s);
if (level[t] < 0) {return flow;}
memset(iter, 0, sizeof iter);
int f;
while ((f = dfs(s, t, inf)) > 0) {
flow += f;
}
}
}
//elegance~
void printpath(int id) {
if (id < 0) return;
printf("%d ", id);
for (int i = 0; i < G[id].size(); i++)
if(vis[G[id][i].to] && !G[id][i].cap)
printpath(G[id][i].to - n);
}
int main() {
scanf("%d%d", &n, &e);
for (int i = 1, a, b; i <= e; i++) {
scanf("%d%d", &a, &b);
add_edge(a, b + n, 1);
}
for (int i = 1; i <= n; i++) {
add_edge(0, i, 1);
add_edge(n + i, 2 * n + 1, 1);
}
int ans = max_flow(0, 2 * n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < G[i].size(); j++) {
if (!G[i][j].cap) vis[G[i][j].to] = true;
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i + n]) {printpath(i); printf("\n");}
}
printf("%d",n - ans);
return 0;
}数字梯形
比较经典的关于建模思维的题目。
题目大意是，给出一个梯形，要根据下列要求，求m条从顶到底的路径的最大的权和。
- 从梯形的顶至底的 m 条路径互不相交；
- 从梯形的顶至底的 m 条路径仅在数字结点处相交；
- 从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。
问题就在于如何将这三个子问题转换为网络流模型。
网络流的建模，拆点可能是最有用的方法了。我们将每一个点拆成两个（小）点\(x_i, y_i\) 并连边，容量随子任务要求不同而不同，费用始终为这个点的权值；对于梯形上下点之间的连边，总是用\(y_i\)去连接\(x_j\) ，容量随子任务要求不同而不同， 费用始终为0。用一个超级源点连接顶层，容量只能为1（按照题目要求），费用总为0；一个超级汇点承接底层，容量随子任务要求不同而不同，费用总为0。
对于子任务1，m条路径互不相交，即点、边均不能有重复。那么就将\(x_i, y_i\)之间连一条容量为1的边，这样就会防止点相交。而对于边，为了不让其相交，我们可以将梯形上下点的连边的容量修改为1，边即可无交。超级根与梯形的所有连边容量都必须是1.
对于子任务2，类比子任务1，允许在数字结点处相交即意味着\(x_i, y_i\)之间的容量可以为无限大，这样就允许了点重合。超级汇点与梯形底层所连接的所有边容量设置为无穷大。
对于子任务3，类比前两个任务，只需要将梯形上下的边的容量也修改成无穷大就OK。
Code：
//数字梯形
#include <bits/stdc++.h>
#define MAXN 900 + 10
#define p(x) printf("%d", (x))
#define pl printf("\n")
#define db printf("working\n")
using namespace std;
const int inf = 0x3f3f3f3f;
typedef pair<int, int > P;
struct edge{
int to, cap, cost, rev;
};
vector<edge> G[MAXN];
int dist[MAXN]; int V, n, m, cnt, s, t;
int val[MAXN][MAXN], prevv[MAXN], preve[MAXN], h[MAXN], x[MAXN][MAXN], y[MAXN][MAXN];
void add_edge(int from, int to, int cap, int cost) {
G[from].push_back((edge){to, cap, cost, G[to].size()});
G[to].push_back((edge{from, 0, -cost, G[from].size() - 1}));
}
inline void clear() {
for (int i = 0; i < MAXN; i++) G[i].clear();
}
//O(FEV) ~O(FV^2)
/*
int min_cost_flow(int s, int t, int f) {
int res = 0;
fill(h, h + V, 0);
while (f > 0) {
priority_queue<P, vector<P> ,greater<P> > que;
fill(dist, dist + V, inf);
que.push(P(0, s));
dist[s] = 0;
while (!que.empty()) {
P p = que.top(); que.pop();
int v = p.second;
if (dist[v] < p.first) continue;
for (int i = 0; i < G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
que.push(P(dist[e.to], e.to));
//db;
}
}
}
if (dist[t] == inf) return -1;
for (int v = 0; v < V; v++) h[v] += dist[v];
int d = f;
for (int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][preve[v]].cap);
f -= d;
res += d * h[t];
for (int v = t; v != s; v = prevv[v]) {
edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
}
*/
int min_cost_flow(int s, int t, int f) {
int res = 0;
while (f > 0) {
fill(dist, dist + V, inf);
dist[s] = 0;
bool update = true;
while (update) {
update = false;
for (int v = 0; v <= V; v++) {
if (dist[v] == inf) continue;
for (int i = 0; i < G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
//db;
}
}
//db;
}
//db;
}
if (dist[t] == inf) return -1;
int d = inf;
for (int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][preve[v]].cap);
f -= d;
res += d * dist[t];
for (int v = t; v != s; v = prevv[v]) {
edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[e.to][e.rev].cap += d;
}
}
return res;
}
//从梯形的顶至底的 m 条路径互不相交
int solve1() {
clear();
for (int i = 1; i <= m; i++) add_edge(s, x[1][i], 1, 0);
for (int i = 1; i <= m + n - 1; i++) add_edge(y[n][i], t, 1, 0);
for (int i = 1; i <= n; i++) for(int j = 1; j <= m + i - 1; j++) add_edge(x[i][j], y[i][j], 1, -val[i][j]);
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m + i - 1; j++) {
add_edge(y[i][j], x[i + 1][j], 1, 0);
add_edge(y[i][j], x[i + 1][j + 1], 1, 0);
}
}
return min_cost_flow(s, t, m);
}
int solve2() {
clear();
for (int i = 1; i <= m; i++) add_edge(s, x[1][i], 1, 0);
for (int i = 1; i <= m + n - 1; i++) add_edge(y[n][i], t, inf, 0);
for (int i = 1; i <= n; i++) for(int j = 1; j <= m + i - 1; j++) add_edge(x[i][j], y[i][j], inf, -val[i][j]);
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m + i - 1; j++) {
add_edge(y[i][j], x[i + 1][j], 1, 0);
add_edge(y[i][j], x[i + 1][j + 1], 1, 0);
}
}
return min_cost_flow(s, t, m);
}
int solve3() {
clear();
for (int i = 1; i <= m; i++) add_edge(s, x[1][i], 1, 0);
for (int i = 1; i <= m + n - 1; i++) add_edge(y[n][i], t, inf, 0);
for (int i = 1; i <= n; i++) for(int j = 1; j <= m + i - 1; j++) add_edge(x[i][j], y[i][j], inf, -val[i][j]);
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m + i - 1; j++) {
add_edge(y[i][j], x[i + 1][j], inf, 0);
add_edge(y[i][j], x[i + 1][j + 1], inf, 0);
}
}
return min_cost_flow(s, t, m);
}
int main() {
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m + i - 1; j++) {
cnt++;
scanf("%d", &val[i][j]);
x[i][j] = cnt * 2 - 1;
y[i][j] = cnt * 2;
}
}
V = 2 * cnt + 2; s = 0; t = 2 * cnt + 1;
p(-solve1()); pl; p(-solve2()); pl; p(-solve3());
return 0;
}题目要求的是最大费用流，只用把原边权值改为负然后最后答案改为负就OK。
星际转移
这应该是最有价值的一题。在大佬们的启发下我终于有了思路…
题目的一个难点就是太空船是周期性停靠的。
正解是写不出来的，这辈子都写不出正解的。复杂的数据结构和数学又不会，就是枚举和暴力这种东西，才能勉强A几道水题。
大致思路：按照天数加边，求分层图最大流的每天的累加直到答案为人数（因为网络流的特性就是图有加边不用重构只用在原基础上增广）。每过一天多一层。注意一下，因为人员可以“滞留”，所以这一天的星球/空间站要和下一天的星球/空间站连边，容量无限。至于如何表达在不同天数下的各星球状态，只用采用一种方法让其不重复就OK。如果有信心随机都没问题，反正又不追加查询
Code：
#include <bits/stdc++.h>
#define MAXN 100 + 10
#define MAXM 500000 + 3
#define db printf("working\n")
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, e, k, s, t;
int par[MAXN], h[MAXN], per[MAXN][MAXN], cnt[MAXN];
struct edge {
int to, cap, rev;
};
namespace MAX_FLOW {
int level[MAXM], iter[MAXM], vis[MAXM];
vector<edge> G[MAXM];
void add_edge(int from, int to, int cap) {
G[from].push_back((edge) {to, cap, G[to].size()});
G[to].push_back((edge) {from, 0, G[from].size() - 1});
//db;
}
void bfs(int s) {
memset(level, -1, sizeof level);
queue<int> que;
que.push(s);
level[s] = 0;
while (!que.empty()) {
int v = que.front();
que.pop();
for (int i = 0; i < G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
//db;
}
}
}
}
int dfs(int v, int t, int f) {
if (v == t) return f;
for (int &i = iter[v]; i < G[v].size(); i++) {
edge &e = G[v][i];
if(e.cap > 0 && level[e.to] > level[v]) {
int d = dfs(e.to, t, min(e.cap, f));
if (d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int max_flow(int s, int t) {
int flow = 0;
while (true) {
bfs(s);
if(level[t] < 0) return flow;
memset(iter, 0, sizeof iter);
int f;
while ((f = dfs(s, t, inf)) > 0) {
flow += f;
}
}
}
}
namespace unionset {
inline int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]);
}
inline void pre() {
for (int i = 1; i < MAXN; i++) par[i] = i;
}
}
using namespace unionset;
inline int hasher(int x, int y) {
return y * (n + 2) + x;
}
void init() {
int earth = 2, moon = 1, ans = 0, cur = 0;
MAX_FLOW::add_edge(s, hasher(earth, 0), k);
MAX_FLOW::add_edge(hasher(moon, 0), t, 0);
for (;;) {
cur++;
for (int i = 1; i <= n + 2; i++) {
MAX_FLOW::add_edge(hasher(i, cur - 1), hasher(i, cur), inf);
}
for (int i = 1; i <= m; i++) {
MAX_FLOW::add_edge(hasher(per[i][(cur - 1) % cnt[i]], cur - 1), hasher(per[i][cur % cnt[i]], cur), h[i]);
}
MAX_FLOW::add_edge(hasher(moon, cur), t, inf);
ans += MAX_FLOW::max_flow(s, t);
if (ans == k) {
printf("%d\n", cur); break;
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
pre();
s = 0; t = n * (n + 2) * (m + 1) * k * 2 + 1;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &h[i], &cnt[i]);
for (int j = 0; j < cnt[i]; j++) {
scanf("%d", &per[i][j]);
per[i][j] += 2;
if (j) {
int x = find(per[i][j - 1]);
int y = find(per[i][j]);
if (x != y) par[x] = y;
}
}
}
int moon = 1, earth = 2;
if (find(earth) != find(moon)) {
printf("%d\n", 0);
// printf("%d %d", find(earth), find(moon));
}
else init();
return 0;
}疏漏错误请评论。
xD.