抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

闲话

基于本题已经有人写了匈牙利的题解,这里我就来写一篇关于网络流的题解。

能做这道题的人应该都能看出是裸的最小重复路径覆盖问题吧。

虽然最小路径覆盖原代码只会红一个点。

思路

首先网络流的难点一直都是在于建图,那么这道题该怎么建图呢?

引入

先想一下普通的最小路径覆盖集问题,我们的见图方式是将每个点拆为出点和入点,目的是保证每个点刚好只被所有路径经过一次。

然后将源点和入点连接,汇点和出点连接(废话)。

对于原图中的连边 我们将 出点连接到 入点。

仔细考虑一下为什么这么建图,我的解释是这样的:对于最小路径覆盖我们肯定希望能用最少的路径覆盖不重不漏覆盖所有点,那么上面这种建图方式,可以再实际运行中像穿针引线一样把所有这条路径上是点用 的单位流量穿起来从起点引导到终点,而因为过程中限流,所以就算有多条边和改点相连,最后也只会穿到一条路径上,而跑满最大流的过程最好就是将上面所有的边 都跑上一的流量,刚好满足最大流的性质。

正解

最小路径覆盖和最小重复路径覆盖的区别在于,后者可以是一条边被多次覆盖,那该怎么办呢?

其实唯一区别就是将原来的建边改为将一个点和它所有能沿着当前边能到达的点都连上有向边

现在考虑为什么?

因为是重复覆盖,因此可以有多条路径同起点或同终点,而原来一条路径可能会被另一条分成两条,而现在可以直接用两点表示一整条路径,故上述建图方式可行。

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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/*
g++ -o2 P10938.cpp -o c -std=c++14
.\c

*/

#include<cstring>
#include<vector>
#include<cstdio>

using namespace std;
const int N=4e2+20;
const int M=5e4+100;
const int inf=0x3f3f3f3f;

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline int ops(int x){return x^1;}

int tot;
int head[N];
struct edge{
int y,f,w;
int next;
}e[M];

int cur[N];
int dep[N];

int q[M];
int in[N];
int ou[N];

int n,m;
int s,t;

int con[N][N];
vector<int>v[N];

char *p1,*p2;
char buf[10];
// #define nc getchar
#define nc() (p1==p1 && (p2=(p1=buf)+fread(buf,1,10,stdin),p1==p2)?EOF:*p1++)

inline void read(int &x){
int sum=0;
char ch=nc();
while(ch<48 || ch>57){
ch=nc();
}
while(ch>=48 && ch<=57){
sum=(sum<<3)+(sum<<1)+ch-48;
ch=nc();
}
x=sum;
return ;
}

inline void add(int x,int y,int f){
e[tot].y=y;
e[tot].f=f;
e[tot].next=head[x];
head[x]=tot++;
return ;
}

inline void make(int x,int y,int f){
add(x,y,f);
add(y,x,0);
return ;
}

inline bool bfs(int start,int to){
int hh=0;
int tt=1;
memset(dep,-1,sizeof(dep));
// for(int i=1;i<=n*2+10;i++)dep[i]=-1;
q[hh]=start;
cur[start]=head[start];
dep[start]=0;
while(hh!=tt){
int x=q[hh++];
if(tt==M)hh=0;
for(int i=head[x];~i;i=e[i].next){
int y=e[i].y;
int f=e[i].f;
if(!f)continue;
if(dep[y]==-1){
dep[y]=dep[x]+1;
cur[y]=head[y];
if(y==to)return true;
q[tt++]=y;
if(tt==M)tt=0;
}
}
}
return false;
}

inline int find(int x,int to,int limit){
if(x==to)return limit;
int flow=0;
for(int i=cur[x];~i && flow<limit;i=e[i].next){
int y=e[i].y;
int f=e[i].f;
cur[x]=i;
if(!f)continue;
if(dep[y]==dep[x]+1){
int t=find(y,to,min(limit-flow,f));
if(!t)dep[y]=-1;
e[i].f-=t;
e[ops(i)].f+=t;
flow+=t;
}
}
return flow;
}

inline void dinic(int start,int to,int &ans){
int flow=0;
int r=0;
while(bfs(start,to)){
while(flow=find(start,to,inf)){
r+=flow;
}
}
ans=r;
return ;
}

inline void init(){
tot=0;
memset(head,-1,sizeof(head));
s=0;
t=n*2+1;
return ;
}

inline void debug_build(){
for(int i=0;i<tot;i+=2){
int x=e[ops(i)].y;
// int x=e[i].x;
int y=e[i].y;
int f=e[i].f;
// int w=e[i].w;
printf("%d -> %d :%d\n",x,y,f);
}
return ;
}

inline void dfs(int x,int fro){
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(con[fro][y])continue;
con[fro][y]=1;
// con[y][fro]=1;
dfs(y,fro);
}
return ;
}

int main(){
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
for(int i=1;i<=n;i++){
dfs(i,i);
for(int j=1;j<=n;j++){
if(con[i][j]){
make(i+n,j,1);
}
}
}
for(int i=1;i<=n;i++){
make(s,i+n,1);
make(i,t,1);
}
int ans;
// debug_build();
dinic(s,t,ans);
printf("%d\n",n-ans);
return 0;
}

最后祝喜欢瓦尼瓦尼的 能早日水神满命。