翻车笔记_ 最小路径覆盖问题 [网络流, 最小路径覆盖, 二分图]

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈老娘要放假啦

懵逼的 题目

传送至 Luogu

扯淡的 题解

最小路径覆盖, 就是在一个DAG里面找出最少的几条不相交路径, 使这些路径包含DAG里的所有点…
这里的不相交有两种情况:

1. 严格不相交, 即不能有一个节点在不同路径上出现
2. 非严格不相交, 即点可以重复出现, 当然边也可以...
  1. 严格不想交的情况可以转化为二分图解决, 把每个点裂成两个(注意, 裂点是网络流常用技巧…), 比如说x1, x2, 那么对于每一条有向边(x, y), 我们可以在二分图中这样连x1 -> y2然后就得到一个二分图, n - 二分图的最大匹配数 = 最小路径覆盖的路径条数
    因为在二分图中多匹配一条边, 就相当于在原图中把两条路径覆盖联结成一个, 覆盖数减少了1 (设开始的时候一个点就是一个覆盖ans = n;, 这时就可以ans--;), 所以n - 二分图的最大匹配数 = 最小路径覆盖的路径条数Emmmmmmmm…

  2. 非严格的话…就是Floyd一下…判断两个点在有向图中是否能到达, 就可以把每两个点之间连边了…然后就和上面的一样了…
    想一想…如果允许边重复出现, 是不是就相当于Floyd走了”中间节点”…所以说Floyd的作用就是把原图中相隔比较远的(中间的节点可能被其他路径覆盖而不能再次覆盖)两个节点间连一条边, 把两个节点的距离”缩短”, 从而达到非严格转变为严格的目的…

注意几个细节…

  • 连边的时候要注意from节点是否已经和s之间有边了…
  • 记录路径的时候注意判断每条边的from是不是s…否则会覆盖掉一些记录前驱的数组(to当然也要判断是不是 == t)…

沙茶的 代码

就是上面的细节没注意改了好久(O(Day2))…

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define MAXN (1600 + 5)
#define INF (0x7ffffff)
#define MAXM (30000 + 5)
#define rev(a) (((a - 1) ^ 1) + 1)
#define cor(a) ((a) + (MAXN))
#define rec(a) ((a > MAXN) ? (a - MAXN) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int s = 0, t = MAXN * 2 - 1;
struct edg
{
int from;
int to;
int next;
int cap;
int flow;
edg() {}
edg(int fr, int t, int ne, int c, int fl): from(fr), to(t), next(ne), cap(c), flow(fl) {}
} b[MAXM << 1];
int cntb = 0;
int g[MAXN << 1];

int n;
int m;
int dis[(MAXN << 1) + 5];
int nex[MAXN];
int pre[MAXN];
int cnt = 0;
int out[MAXN << 1][MAXN << 1];
void adn(int, int, int);
int mach(int);
int dinic(int, int);
bool bfs();
void solve();
void initout();
void init();
void dfs(int, int);
int main()
{
init();
solve();
return 0;
}
void init()
{
scanf("%d%d", &n, &m);
int srx, sry;
bool vis[MAXN << 1];
memset(vis, false, sizeof(vis));
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
adn(srx, cor(sry), 1);
adn(cor(sry), srx, 0);
if (!vis[srx])
{
adn(s, srx, 1);
adn(srx, s, 0);
vis[srx] = true;
}
if (!vis[cor(sry)])
{
adn(cor(sry), t, 1);
adn(t, cor(sry), 0);
vis[cor(sry)] = true;
}
}
}
void adn(int fr, int to, int ca)
{
b[++cntb] = edg(fr, to, g[fr], ca, 0);
g[fr] = cntb;
}
void solve()
{
int re = 0;
while (bfs())
{
re += dinic(s, INF);
}
initout();
for (int i = 1; i <= cnt; i++)
{
for (int j = 1; j <= out[i][0]; j++)
{
printf("%d ", out[i][j]);
}
puts("");
}
printf("%d", cnt);
}
int dinic(int dq, int maxf)
{
if (dq == t || (!maxf))
return maxf;
int re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if ((dis[b[i].to] == dis[dq] + 1) && (b[i].cap - b[i].flow > 0))
{
int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
maxf -= zl;
b[i].flow += zl;
b[rev(i)].flow -= zl;
re += zl;
/*if (zl > 0 && b[i].to != t)
nex[rec(dq)] = rec(b[i].to), pre[rec(b[i].to)] = rec(dq);*/
}
}
return re;
}
bool bfs()
{
memset(dis, 0, sizeof(dis));
dis[s] = 1;
queue<int> q;
q.push(s);
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
if ((!dis[b[i].to]) && b[i].cap - b[i].flow > 0)
{
dis[b[i].to] = dis[dq] + 1;
q.push(b[i].to);
}
}
}
return dis[t];
}
void initout()
{
for (int i = 1; i <= cntb; i++)
{
if (b[i].from != s && b[i].cap == b[i].flow && b[i].cap == 1 && b[i].to != t)
{
pre[rec(b[i].to)] = rec(b[i].from);
nex[rec(b[i].from)] = rec(b[i].to);
}
}
memset(out, 0, sizeof(out));
bool v[MAXN];
memset(v, false, sizeof(v));
for (int i = 1; i <= n; i++)
{
if (!v[i])
{
v[i] = true;
++cnt;
int dq = i;
v[dq] = true;
out[cnt][++out[cnt][0]] = dq;
while (nex[dq] && pre[nex[dq]] == dq)
{
dq = nex[dq];
v[dq] = true;
out[cnt][++out[cnt][0]] = dq;
}
}
}
}

By 不想月考的 Cansult