【PowerOJ1738】最小路径覆盖

给定有向图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 行开始，每行输出一条路径。文件的最后一行是最少路径数。

Sample Input

11 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

Sample Output

4 7 10 11 2 5 8 3 6 9 3
 
题解：
每一个点拆成i和i+n两个，每一个表示他在边中是前驱还是后继，然后所有的前驱init（S，i，1）所有的后继（i+n，T，1）
每一条边（u，v）改成u的前驱到v的后继有一条（u，v+n，INF）的边
然后答案为n-最大流
然后输出路径，已知路径的开始一定后继没有被访问过，所以i+n到T的边依旧为1，可以找出所有路径的开始节点。
然后就是判断他和哪些边匹配过,不断递归输出.
细节很巧妙，详情看代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1005,M=200005,INF=1999999999;
int gi(){
   int str=0;char ch=getchar();
   while(ch>'9' || ch<'0')ch=getchar();
   while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();
   return str;
}
int n,m,num=1,head[N],S=0,T,d[N];
struct Lin{
   int next,to,dis;
}a[M];
void init(int x,int y,int z){
   a[++num].next=head[x];
   a[num].to=y;
   a[num].dis=z;
   head[x]=num;
   a[++num].next=head[y];
   a[num].to=x;
   a[num].dis=0;
   head[y]=num;
}
int q[N],dep[N];
bool bfs()
{
   memset(dep,0,sizeof(dep));
   q[1]=S;dep[S]=1;
   int x,u,t=0,sum=1;
   while(t!=sum)
   {
       x=q[++t];
       for(int i=head[x];i;i=a[i].next){
           u=a[i].to;
           if(dep[u] || a[i].dis<=0)continue;
           dep[u]=dep[x]+1;q[++sum]=u;
       }
   }
   return dep[T];
}
int dfs(int x,int flow)
{
   if(T==x || !flow)return flow;
   int u,tmp,tot=0;
   for(int i=head[x];i;i=a[i].next){
       u=a[i].to;
       if(dep[u]!=dep[x]+1 || a[i].dis<=0)continue;
       tmp=dfs(u,min(a[i].dis,flow));
       tot+=tmp;flow-=tmp;
       a[i].dis-=tmp;a[i^1].dis+=tmp;
       if(!flow)break;
   }
   return tot;
}
int maxflow()
{
   int tmp,tot=0;
   while(bfs()){
       tmp=dfs(S,INF);
       while(tmp)tot+=tmp,tmp=dfs(S,INF);
   }
   return tot;
}
void hfs(){
   int u;
   for(int i=head[T];i;i=a[i].next){
       if(!a[i].dis)d[a[i].to]=true;
   }
}
void Print(int x)
{
   printf("%d ",x);
   for(int i=head[x];i;i=a[i].next){
       if(a[i].to!=S && a[i].dis==INF-1)Print(a[i].to-n);
   }
}
int main()
{
   int x,y;
   n=gi();m=gi();
   T=2*n+1;
   for(int i=1;i<=n;i++)init(S,i,1),init(i+n,T,1);
   for(int i=1;i<=m;i++){
       x=gi();y=gi();
       init(x,y+n,INF);
   }
   int tp=maxflow();
   hfs();
   for(int i=1;i<=n;i++){
       if(!d[i+n])continue;
       Print(i);
       printf("
");
   }
   printf("%d",n-tp);
}

【PowerOJ1738】最小路径覆盖

Description

Input

Output