题解：P10938 Vani和Cl2捉迷藏
Stairs_upon_temple · · 题解
闲话
基于本题已经有人写了匈牙利的题解，这里我就来写一篇关于网络流的题解。
能做这道题的人应该都能看出是裸的最小重复路径覆盖问题吧。
虽然最小路径覆盖原代码只会红一个点。
思路
首先网络流的难点一直都是在于建图，那么这道题该怎么建图呢？
引入
先想一下普通的最小路径覆盖集问题，我们的见图方式是将每个点拆为出点和入点，目的是保证每个点刚好只被所有路径经过一次。
然后将源点和入点连接，汇点和出点连接（废话）。
对于原图中的连边
仔细考虑一下为什么这么建图，我的解释是这样的：对于最小路径覆盖我们肯定希望能用最少的路径覆盖不重不漏覆盖所有点，那么上面这种建图方式，可以再实际运行中像穿针引线一样把所有这条路径上是点用
正解
最小路径覆盖和最小重复路径覆盖的区别在于，后者可以是一条边被多次覆盖，那该怎么办呢？
其实唯一区别就是将原来的建边改为将一个点和它所有能沿着当前边能到达的点都连上有向边。
现在考虑为什么？
因为是重复覆盖，因此可以有多条路径同起点或同终点，而原来一条路径可能会被另一条分成两条，而现在可以直接用两点表示一整条路径，故上述建图方式可行。
/*
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;
}最后祝喜欢瓦尼瓦尼的