标签：最大流
Solution
首先考虑原图上有 \(n\) 条路径，每条路径只覆盖一个点。现在我们需要将尽可能多的路径合并在一起，得到最小覆盖路径。
那么考虑如何建模：
将每个点拆成 \(X_i\) 与 \(Y_i\) 两个点，分别表示该点的出点与入点。对于原图的边 \(<i,j>\) ，即连接 \(<X_i,Y_j>\)。
如此操作后得到一张二分图。左部点为出点，右部点为入点。
发现对于边 \(<X_i,Y_j>\) 的含义，其实就是将 \(i\) 所在路径与 \(j\) 所在路径合并在一起。
而我们需要将尽可能多的路径合并，即尽可能多的连边；同时每个点只能和其它点合并一次，即只能连一条边。
如此，问题就转化为二分图最大匹配。
所以，只需用网络流求出这张二分图的最大匹配数即可。
从源点 \(S\) 往所有左部点 \(X_i\) 连一条容量为 \(1\) 的边；从右部点 \(Y_i\) 往汇点 \(T\) 连一条容量为 \(1\) 的边；对于 \(<X_i,Y_j>\) ，使其容量为 \(1\)。
跑一边最大流得到的最大流量 \(res\) 即为最大匹配数。因为合并一次路径后路径总数会减一，故最后答案为 \(n - res\)。
最后，对于构造方案，遍历所有 \(<X_i,Y_j>\)，若其容量为 \(0\)，说明 \(X_i\) 与 \(Y_j\) 匹配，即最终方案中 \(i\)，\(j\) 之间相连。如此便可以得到方案。
Code
#include<bits/stdc++.h>
#define M 12605
#define N 305
using namespace std;
typedef long long ll;
typedef double db;
char IO;
int rd(){
int num=0;bool f=0;
while(IO=getchar(),IO<48||IO>57)if(IO==‘-‘)f=1;
do num=(num<<1)+(num<<3)+(IO^48);
while(IO=getchar(),IO>=48&&IO<=57);
return f?-num:num;
}
int to[M],nxt[M],val[M],hd[N],cnte=1;
void Adde(int u,int v,int w){
to[++cnte]=v;val[cnte]=w;
nxt[cnte]=hd[u];hd[u]=cnte;
}
void Add(int u,int v,int w){
Adde(u,v,w);Adde(v,u,0);
}
int n,m,S,T;
int dep[N],cur[N];
queue<int> Q;
int BFS(){
memset(dep,0,sizeof(dep));
memcpy(cur,hd,sizeof(cur));
dep[S]=1;Q.push(S);
int u,v;
while(!Q.empty()){
u=Q.front();Q.pop();
for(int i=hd[u];i;i=nxt[i]){
if(!dep[v=to[i]]&&val[i])
dep[v]=dep[u]+1,Q.push(v);
}
}
return dep[T];
}
int DFS(int u,int flow){
if(u==T)return flow;
int f,res=0;int v;
for(int i=cur[u];i&&flow;i=nxt[i]){
cur[u]=i;v=to[i];
if(dep[v]!=dep[u]+1)continue;
if(val[i]&&(f=DFS(v,min(flow,val[i])))>0){
val[i]-=f;
val[i^1]+=f;
res+=f;flow-=f;
}
}
if(!res)dep[u]=0;
return res;
}
int Lst[N],Nxt[N];
void Find(int u){
if(!u)return ;
printf("%d ",u);
Find(Nxt[u]);
}
int main(){
n=rd(),m=rd(),S=0,T=2*n+1;
for(int i=1;i<=n;++i)
Add(S,i+n,1),Add(i,T,1);
int tmp=cnte;
for(int i=1,u,v,w;i<=m;++i){
u=rd(),v=rd();
Add(u+n,v,1);
}
int res=0;
while(BFS())
res+=DFS(S,1e9);
for(int i=tmp+1,u,v;i<=cnte;i+=2){
v=to[i],u=to[i^1]-n;
if(!val[i])Lst[v]=u,Nxt[u]=v;
}
for(int i=1;i<=n;++i){
if(!Lst[i]){
Find(i);
puts("");
}
}
cout<<n-res;
return 0;
}