题面
给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个定点恰好在$P$的一条路上，则称 $P$ 是 $G$ 的一个路径覆盖。$P$中路径可以从 $V$ 的任何一个定点开始，长度也是任意的，特别地，可以为 $0$ 。$G$ 的最小路径覆盖是 $G$ 所含路径条数最少的路径覆盖。设计一个有效算法求一个 GAP (有向无环图) $G$ 的最小路径覆盖。
提示：设 $V=\{1,2,…,n\}$ ，构造网络 $G_1=\{V_1,E_1\}$ 如下： $$V_1=\{x_0,x_1,…,x_n\}\cup\{y_0,y_1,…,y_n\}$$ $$E_1=\{(x_0,x_i):i\in V\}\cup\{(y_i,y_0):i\in V\}\cup\{(x_i,y_j):(i,j)\in E\}$$ 每条边的容量均为 $1$ ，求网络 $G_1$ 的 $(x_0,y_0)$ 最大流。
一句话题面：给出一张图，用 $k$ 条链去覆盖它，求出最少的链数和覆盖方案。
输入输出格式
输入格式
第一行有 $2$ 个正整数 $n$ 和 $m$ 。 $n$ 是给定$\text{GAP}$(有向无环图) $G$ 的顶点数， $m$ 是 $G$ 的边数。接下来的 $m$ 行,每行有两个正整数 $i$ 和 $j$ 表示一条有向边 $(i,j)$。
输出格式
从第 1 行开始，每行输出一条路径。文件的最后一行是最少路径数。
思路
对于一个点 $i$，将其拆成 $x_i,y_i$ 两个点。所有 $x_i$ 连接源点 $S$，所有 $y_i$ 连接汇点 $T$。
对于一条边 $(u,v)$，连边 $x_u,x_v$。
现在这张图变成了一张二分图，二分图中，最小路径覆盖 = 点的总数 – 网络最大流
最后从 $S$ 到 $T$ 跑一遍最大流。
证明
选出 $k$ 条链，也就是选出 $k$ 个集合，每个集合中的点的度数最多为 $2$。
对于一个点 $i$，当边 $(S,x_i)$ 和 $(y_i,T)$ 都被用掉时，这个点就不可能再被选，这就保证了每个点度数最多为 $2$。增广路只会经过两个节点，在同一集合中。
代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,last[200005],to[200005],nextt[200005],s[200005],top=1;
long long v[200005],d[200005],from[200005];
long long fa[200005];
void reset(){
for (int i=1;i<=200000;i++){
fa[i]=i;
}
}
int getfa(int x){
return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
void merge(int x,int y){
fa[getfa(y)]=getfa(x);
}
void add(int a,int b,int c){
nextt[++top]=last[a];
from[top]=a;
to[top]=b;
s[top]=c;
last[a]=top;
}
bool bfs(long long S,long long T){
memset(v,0,sizeof(v));
memset(d,63,sizeof(d));
queue<long long> q;
q.push(S);
v[S]=1;
d[S]=0;
while (!q.empty()){
long long now=q.front();
q.pop();
v[now]=0;
for (int i=last[now];i;i=nextt[i]){
int j=to[i];
if (d[j]>d[now]&&s[i]){
d[j]=d[now]+1;
if (!v[j]){
q.push(j);
v[j]=1;
}
}
}
}
if (d[T]<1000000000){
return 1;
}
return 0;
}
int dfs(long long x,long long minn,long long T){
if (x==T){
return minn;
}
int tmp=0;
for (int i=last[x];i;i=nextt[i]){
int j=to[i];
if (d[j]==d[x]+1&&s[i]){
tmp=dfs(j,min(minn,s[i]),T);
if (tmp){
s[i]-=tmp;
s[i^1]+=tmp;
return tmp;
}
}
}
return 0;
}
long long dinic(long long S,long long T){
long long ans=0,tmp=0;
while (bfs(S,T)){
while (1){
tmp=dfs(S,2147483647,T);
if (!tmp){
break;
}
ans+=tmp;
}
}
reset();
for (int i=1;i<=top;i++){
if (s[i]==0&&from[i]>=1&&from[i]<=n&&to[i]>=n+1&&to[i]<=n*2){
merge(from[i],to[i]-n);
}
}
return ans;
}
int main(){
reset();
long long S=301,T=302;
cin>>n>>m;
for (int i=1;i<=n;i++){
add(S,i,1);
add(i,S,0);
add(n+i,T,1);
add(T,n+i,0);
}
for (int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,n+b,1);
add(n+b,a,0);
}
bfs(S,T);
dinic(S,T);
int cnt=0;
for (int i=1;i<=n;i++){
bool e=0;
for (int j=1;j<=n;j++){
if (getfa(j)==i){
cout<<j<<" ";
e=1;
}
}
if (e){
cnt++;
cout<<endl;
}
}
cout<<cnt<<endl;
}
