「网络流24题」最小路径覆盖问题-题解

题目传送门: 「Luogu P2764」最小路径覆盖问题

题目大意

题目描述给的很直白,输入点数边数和有向边,输出最少路径数和路径

题解

正常建图
如果一条路径的终点和另一条路径的起点有连边,那么这两条路径是可以合并的。
但是一个终点或起点只能使用一次。比如三条路径$1 \rightarrow 3, 2 \rightarrow 3, 3 \rightarrow 4$,你只能合并两条。
那么这道题就转化为了:最大化一个边集,使得边集中每个起点和终点都只使用过一次。即__最大独立边集__。
把每个点拆成入点$x$和出点$x’$,从源点到$x’$连一条容量为$1$的边,从$x$到汇点连一条容量为$1$的边。边权用来限制每个起点或终点的使用次数。
对于每条边$x \rightarrow y$,连接$x’ \rightarrow y$
答案是$n-最大流$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;

bool vis[maxn], vst[maxn];
int n, m, s, t;
int d[maxn], cur[maxn], to[maxn];

struct Edge {
int from, to, cap, flow;
Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

vector<Edge> edges;
vector<int> G[maxn];

void add(int u, int v, int c) {
edges.push_back(Edge(u, v, c, 0));
edges.push_back(Edge(v, u, 0, 0));
int mm = edges.size();
G[u].push_back(mm - 2);
G[v].push_back(mm - 1);
}

bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(s);
d[s] = 0;
vis[s] = true;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); ++i) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = true;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}

int dfs(int x, int a) {
if (x == t || a == 0) return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); ++i) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
to[x] = e.to;
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
}

int maxflow(int s, int t) {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, inf);
}
return flow;
}

int main() {
scanf("%d %d", &n, &m);
s = 0; t = 2 * n + 1;
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d %d", &u, &v);
add(u, v + n, 1);
}
for (int i = 1; i <= n; ++i) add(s, i, 1);
for (int i = 1; i <= n; ++i) add(i + n, t, 1);
int ans = maxflow(s, t);
for (int i = 1; i <= n; ++i) {
if (!vst[i]) {
int x = i; vst[x] = true;
printf("%d ", x);
while (to[x] && to[x] != t) {
x = to[x] - n;
printf("%d ", x);
vst[x] = true;
}
printf("\n");
}
}
printf("%d\n", n - ans);
return 0;
}

「网络流24题」最小路径覆盖问题-题解

https://blog.tonycrane.cc/p/7973b062.html

作者

TonyCrane

发布于

2019-05-02

更新于

2020-05-05

许可协议

评论