先上题目传送门
最小路径覆盖其实是一类题目，一般用二分图匹配或者网络流都可以做。相关定理：最小路径覆盖数=顶点数-最大割（即最大匹配）
这道题的要求除了求出最小路径覆盖数之外还要求输出每一条路径，这里蒟蒻用的是最简单粗暴的深搜，从每一个路径覆盖的起点开始一个个搜索直到输出所有点。
奉上用Dinic算法做的正解：
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<queue> #include<iostream> #include<algorithm> #define inf 1e9 using namespace std; const int N=10010; int n,m,dis[N<<1],ans; int head[N<<1],size=1; int fa[N<<1],start,endd; struct Node{ int from,to,val,next; }edge[N<<1]; queue<int>team; inline int read() { char ch=getchar();int num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();} while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } inline void add(int x,int y,int z) { edge[++size].from=x; edge[size].to=y; edge[size].val=z; edge[size].next=head[x]; head[x]=size; } inline void add_edge(int x,int y) {add(x,y,1);add(y,x,0);} inline bool bfs() { memset(dis,-1,sizeof(dis)); while(!team.empty())team.pop(); team.push(start);dis[start]=0; while(!team.empty()){ int x=team.front();team.pop(); for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(edge[i].val>0&&dis[y]==-1){ dis[y]=dis[x]+1;team.push(y); } } } return dis[endd]>-1; } inline int dinic(int u,int flow) { if(u==endd||flow==0)return flow; int now=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(edge[i].val>0&&dis[v]==dis[u]+1){ int ka=dinic(v,min(flow-now,edge[i].val)); edge[i].val-=ka; edge[i^1].val+=ka; now+=ka; if(now==flow)break; } } return now; } inline int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);} inline void print(int u) { printf("%d ",u); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(edge[i].val==0&&v>n) print(v-n); } } void ready() { memset(head,-1,sizeof(head)); n=read();m=read();start=0;endd=n<<1|1; for(int i=1;i<=m;i++){ int x=read();int y=read(); add_edge(x,y+n);} for(int i=1;i<=n;i++){ add_edge(start,i); add_edge(i+n,endd); } } void work() { while(bfs()) ans+=dinic(start,inf); for(int i=1;i<=n;i++)fa[i]=i; for(int i=2;i<=size;i++){ int u=edge[i].from,v=edge[i].to; if(u>start&&u<=n&&v>n&&v<endd&&edge[i].val==0) fa[find(v-n)]=find(u);} for(int i=1;i<=n;i++) if(find(i)==i) print(i),printf(" "); printf("%d",n-ans); } int main() { ready(); work(); return 0; }
这里再上一份用二分图匹配算法做的最小路径覆盖模板（不输出路径）：
//It is made by HolseLee on 30th Dec 2017 #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=10010; int n,m,ans,ma[N]; bool vis[N]; vector<int>team[N]; inline int read() { char ch=getchar();int num=0;bool flag=false; while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();} while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();} return flag?-num:num; } inline bool dfs(int u) { for(int i=0;i<team[u].size();i++){ int v=team[u][i]; if(vis[v])continue; vis[v]=true; if(ma[v]==-1||dfs(ma[v])){ ma[v]=u; return true;} } return false; } void ready() { memset(ma,-1,sizeof(ma)); n=read();m=read(); for(int i=1;i<=n;i++) team[i].clear(); for(int i=1;i<=m;i++){ int x=read();int y=read(); team[x].push_back(y); } } void work() { int ret=0; for(int i=1;i<=n;i++){ memset(vis,false,sizeof(vis)); ret+=dfs(i); } ans=n-ret; printf("%d",ans); } int main() { ready(); work(); return 0; }