728. [网络流24题] 最小路径覆盖问题
★★☆ 输入文件：path3.in 输出文件：
path3.out
评测插件
时间限制：1 s 内存限制：128 MB
´问题描述：
给定有向图G=(V,E)。设P是G的一个简单路（顶点不相交）的集合。如果V中每个顶点恰好在P的一条路上，则称P是G的一个路径覆盖。P中路径可以从V的任何一个顶
点开始，长度也是任意的，特别地，可以为0。G的最小路径覆盖是G的所含路径条数最少
的路径覆盖。
设计一个有效算法求一个有向无环图G的最小路径覆盖。
提示：
设V={1，2，... ，n}，构造网络G1=(V1,E1)如下：
每条边的容量均为1。求网络G1的(x0,y0)最大流。
´编程任务：
对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。´数据输入：
由文件input.txt提供输入数据。文件第1行有2个正整数n和m。n是给定有向无环图G的顶点数，m是G的边数。接下来的m行，每行有2个正整数i 和j，表示一条有向边(i,j)。
´结果输出:
程序运行结束时，将最小路径覆盖输出到文件output.txt中。从第1行开始，每行输出一条路径。文件的最后一行是最少路径数。
输入文件示例
input.txt11 12 1 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 11 10 11
输出文件示例
output.txt
1 4 7 10 11 2 5 8 3 6 9 3
数据范围：
1<=n<=150,1<=m<=6000
【问题分析】
有向无环图最小路径覆盖，可以转化成二分图最大匹配问题，从而用最大流解决。
【建模方法】
构造二分图，把原图每个顶点i拆分成二分图X，Y集合中的两个顶点Xi和Yi。对于原图中存在的每条边(i,j)，在二分图中连接边(Xi,Yj)。然后把二分图最大匹配模型转化为网络流模型，求网络最大流。
最小路径覆盖的条数，就是原图顶点数，减去二分图最大匹配数。沿着匹配边查找，就是一个路径上的点，输出所有路径即可。
【建模分析】
对于一个路径覆盖，有如下性质：
1、每个顶点属于且只属于一个路径。
2、路径上除终点外，从每个顶点出发只有一条边指向路径上的另一顶点。
所以我们可以把每个顶点理解成两个顶点，一个是出发，一个是目标，建立二分图模型。该二分图的任何一个匹配方案，都对应了一个路径覆盖方案。如果匹配数为0，那么显然路径数=顶点数。每增加一条匹配边，那么路径覆盖数就减少一个，所以路径数=顶点数 - 匹配数。要想使路径数最少，则应最大化匹配数，所以要求二分图的最大匹配。
注意，此建模方法求最小路径覆盖仅适用于有向无环图，如果有环或是无向图，那么有可能求出的一些环覆盖，而不是路径覆盖。
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<iomanip>
//#define mem(dp,a) memset(dp,a,sizeof(dp))
//#define fo(i,n) for(int i=0;i<(n);i++)
//#define INF 0x3f3f3f3f
#define fread() freopen("data.txt","r",stdin)
#define fwrite() freopen("out.out","w",stdout)
using namespace std;
typedef long long ll;
vector<int> re;
int s,t;
int m,n,t1,t2;
int ans;
const int MAXN=100000,MAXM=100000,inf=1e9;
struct Edge
{
int v,c,f,nx;
Edge() {}
Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}
} E[MAXM];
int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;
int tonex[MAXN];//记录下一个节点
bool vis[MAXN];//
//dis[]层次
void init(int _n) //初始化
{
N=_n,sz=0; memset(G,-1,sizeof(G[0])*N);
}
void link(int u,int v,int c)//连接两个点
{
E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;
E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;
}
int ISAP(int S,int T)
{//S -> T
int maxflow=0,aug=inf,flag=false,u,v;
for (int i=0;i<N;++i)cur[i]=G[i],gap[i]=dis[i]=0;
for (gap[S]=N,u=pre[S]=S;dis[S]<N;flag=false)
{
for (int &it=cur[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[u]==dis[v=E[it].v]+1)
{
if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f;
pre[v]=u,u=v; flag=true;
if (u==T)
{
for (maxflow+=aug;u!=S;)
{
E[cur[u=pre[u]]].f+=aug;
E[cur[u]^1].f-=aug;
}
aug=inf;
}
break;
}
}
if (flag) continue;
int mx=N;
for (int it=G[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[E[it].v]<mx)
{
mx=dis[E[it].v]; cur[u]=it;
}
}
if ((--gap[dis[u]])==0) break;
++gap[dis[u]=mx+1]; u=pre[u];
}
return maxflow;
}
bool bfs(int S,int T)
{
static int Q[MAXN];
memset(dis,-1,sizeof(dis[0])*N);
dis[S]=0;
Q[0]=S;
//dis[i]为-1表示没有
for (int h=0,t=1,u,v,it ; h<t ; ++h)
{
for ( u=Q[h],it=G[u] ; ~it ; it=E[it].nx)
{
if (dis[v=E[it].v]==-1 && E[it].c > E[it].f)
{
dis[v]=dis[u]+1;
Q[t++]=v;
}
}
}
return dis[T]!=-1;
}
int dfs(int u,int T,int low)
{
if (u==T) return low;
int ret=0,tmp,v;
for (int &it=cur[u];~it&&ret<low;it=E[it].nx)
{
if (dis[v=E[it].v]==dis[u]+1&&E[it].c>E[it].f)
{
if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f)))
{
if(v-n>0) vis[v-n]=1;
tonex[u] = v;
ret+=tmp;
E[it].f+=tmp;
E[it^1].f-=tmp;
// low -= tmp;
// if(low==0)break;
}
}
}
if (!ret) dis[u]=-1;
return ret;
}
int dinic(int S,int T)
{
int maxflow=0,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G[0])*N);
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
int main()
{
ios_base::sync_with_stdio(false);
// fread();
freopen("path3.in","r",stdin);
freopen("path3.out","w",stdout);
cin >> n>> m;
s=0; t=n+n+1;
init(t+1);
for(int i=1;i<=n;i++)
{
link(s,i,1);
}
for(int i=n+1;i<=2*n;i++)
{
link(i,t,1);
}
for(int i = 0 ;i < m;i++)
{
cin >> t1 >> t2;
link(t1,t2+n,inf);
}
int tmp_ans = dinic(s,t);
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
cout<<i;
int k=i;
while(tonex[k])
{
cout<<" "<<tonex[k]-n;
k=tonex[k]-n;
}
cout<<endl;
}
cout << n - tmp_ans <<endl;
return 0;
}