设一个有向无环图G =（V,E）,n=|V|。
把G中的每个点x拆成编号为x和x+n的两个点。建立一张新的二分图，1-n做为二分图的左部点，n+1 -> 2n 做为二分图的右部点，对于原图的每条有向边(x,y),在二分图中的左部点x与右部点y+n之间连边。
最终得到的二分图称为G的拆点二分图，记为G2。
定理：
有向无环图G的最小路径点覆盖包含的路径条数，等于n减去拆点二分图G2的最大匹配数。
证明：
详细证明在算法竞赛——进阶指南这本书上。
我简单说下:
最大匹配的每条边对应G中的一条边。而左部图中未匹配的点，一定是一条路径的终点，而一条路径的终点在左部图一定为匹配(因为没有出边)。
有向无环图G的最小路径点覆盖包含的路径条数最少 ---> 让终点最少 --> 所以让未匹配的点数最少 --> 二分图匹配边数最大！
借用洛谷大佬的一张图表示建模：
最后，用求最大流边的方法，求出所有匹配边，然后用并查集维护找到所有路径！
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 8000+7; const int N = 300+7; struct Dinic{ //N个点，M条边 //add建双向边，然后D.gao ,最后输出maxflow #define inf 0x3f3f3f3f ll maxflow;int s,t,n; int v[N],pre[N],d[N],now[N]; ll incf[N]; int head[N],cnt=1; struct EDGE{int to,nxt;ll w;}ee[M*2]; inline void AD(int x,int y,ll w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} inline void add(int x,int y,ll w){AD(x,y,w);AD(y,x,0);} inline bool bfs()//在残量网络上构造分层图 { memset(d,0,sizeof(d)); queue<int>q; q.push(s);d[s]=1; while(q.size()) { int x=q.front();q.pop(); for(int i=head[x];i;i=ee[i].nxt) { int y=ee[i].to;ll w=ee[i].w; if(w&&!d[y]) { q.push(y); d[y]=d[x]+1; if(y==t)return 1; } } } return false; } inline int dinic(int x,int flow) { if(x==t)return flow; ll rest = flow,k; for(int i=now[x];i&&rest;i=ee[i].nxt) { int y=ee[i].to;ll w= ee[i].w; now[x]=i; if(w&&d[y]==d[x]+1) { k=dinic(y,min(rest,w)); if(!k)d[y]=0;//剪枝，去掉增广完毕的点 ee[i].w-=k; ee[i^1].w+=k; rest-=k; } } return flow - rest; } inline void gao() { int flow=0; while(bfs()) { for(int i=0;i<=n;i++)now[i]=head[i]; while(flow=dinic(s,inf))maxflow+=flow; } } inline void init(int nn,int S,int T) { cnt=1;maxflow=0; for(int i=0;i<=n;i++)head[i]=0; s=S,t=T,n=nn; } }D; //求解二分图匹配问题时的复杂度是：m*sqrt(n)的 struct node{ int x,y,id; }p[M];//记录每条边 x -> y 反向边的编号 (cnt) int fa[N]; int gt(int x){ if(fa[x]==x)return x; return fa[x]=gt(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m,s,t; cin>>n>>m; int N=n*2+2; s=2*n+1,t=2*n+2; D.init(N,s,t);//初始化节点个数，起点，终点 for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; D.add(x,y+n,1); p[i]=node{x,y,D.cnt}; } for(int i=1;i<=n;i++)D.add(s,i,1),D.add(i+n,t,1); int flow=0; D.gao(); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++){ if(D.ee[p[i].id].w){//这条边的反向边有流量即改边被最大流选中 //存在一条边 ： p[i].x -> p[i].y 即把与x相连的 和 与y相连的点集 合并 //由于求得的是不相交路径，每个点最多一个入边一个出边，所以最多往前合并一次，往后合并一次 //cout<<" = == = "<<p[i].x<<" "<<p[i].y<<endl; int gx=gt(p[i].x),gy=gt(p[i].y); if(gx!=gy)fa[gx]=gy; } } // for(int i=1;i<=n;i++)cout<<fa[i]<<" "; // cout<<" --------- "<<endl; for(int i=1;i<=n;i++){ bool flag=false; for(int j=1;j<=n;j++){ if(gt(j)==i)cout<<j<<" ",flag=true; } if(flag)cout<<endl; } cout<<n-D.maxflow<<endl; return 0; }