[网络流24题] 最小路径覆盖问题

Description

问题描述：

给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图G 的最小路径覆盖。

编程任务：

对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。

Input Format

文件第1 行有2个正整数n和m。n是给定有向无环图G 的顶点数，m是G 的边数。接下来的m行，每行有2 个正整数i和j，表示一条有向边(i,j)。

Output Format

从第1 行开始，每行输出一条路径(行末无空格)。文件的最后一行是最少路径数。

输入样例#1：

输出样例#1：

1 4 7 10 11
2 5 8
3 6 9
3

这篇博客讲的好我就不写了

http://blog.csdn.net/zhongshijunacm/article/details/22290883

  1 /*
  2     一个点拆成两个
  3     建二分图 跑最大流 表示有多少点可以跑到汇点 
  4     路径数= 顶点数 - 最大匹配数 
  5     最后在打印路径就好了 
  6 */
  7 #include <queue>
  8 #include <ctype.h>
  9 #include <vector>
 10 #include <cstdio>
 11 
 12 const int MAXN=310;
 13 const int INF=0x7fffffff;
 14 
 15 std::vector<int> v[MAXN];
 16 
 17 int n,m,src,decc;
 18 
 19 int f[MAXN][MAXN],depth[MAXN],pre[MAXN],vis[MAXN];
 20 
 21 std::queue<int> q;
 22 
 23 inline void read(int&x) {
 24     register char c=getchar();
 25     for(x=0;!isdigit(c);c=getchar());
 26     for(;isdigit(c);x=x*10+c-48,c=getchar());
 27 }
 28 
 29 inline void add(int x,int y,int val) {
 30     v[x].push_back(y);
 31     f[x][y]=val;
 32 }
 33 
 34 inline int min(int a,int b) {
 35     return a<b?a:b;
 36 }
 37 
 38 bool bfs() {
 39     for(int i=0;i<=n+n+1;++i) depth[i]=-1;
 40     while(!q.empty()) q.pop();
 41     q.push(src);
 42     depth[src]=0;
 43     while(!q.empty()) {
 44         int u=q.front();
 45         q.pop();
 46         for(int i=0;i<v[u].size();++i) {
 47             int to=v[u][i];
 48             if(f[u][to]&&depth[to]==-1) {
 49                 depth[to]=depth[u]+1;
 50                 q.push(to);
 51                 if(to==decc) return true;
 52             }
 53         }
 54     }
 55     return false;
 56 }
 57 
 58 int dfs(int now,int flow) {
 59     if(now==decc) return flow;
 60     int used=0,delat;
 61     for(int i=0;i<v[now].size();++i) {
 62         int to=v[now][i];
 63         if(f[now][to]&&depth[to]==depth[now]+1) {
 64             delat=flow-used;
 65             delat=dfs(to,min(delat,f[now][to]));
 66             f[now][to]-=delat;
 67             f[to][now]+=delat;
 68             used+=delat;
 69             if(used==flow) break;
 70         }
 71     }
 72     if(!used) depth[now]=-1;
 73     return used;
 74 }
 75 
 76 inline void Print_Road(int now) {
 77     for(int i=0;i<v[now].size();++i) {
 78         int to=v[now][i];
 79         if(f[to][now]&&!vis[to]&&to!=src&&to!=decc)
 80           vis[to-n]=true,printf("%d ",to-n),Print_Road(to-n);
 81     }
 82     return;
 83 }
 84 
 85 int hh() {
 86     freopen("path3.in","r",stdin);
 87     freopen("path3.out","w",stdout);
 88     int x,y;
 89     read(n);read(m);
 90     decc=n+n+1;
 91     for(int i=1;i<=m;++i) {
 92         read(x);read(y);
 93         add(x,y+n,1),add(y+n,x,0);
 94     }
 95     for(int i=1;i<=n;++i) {
 96         add(src,i,1),add(i,src,0);
 97         add(i+n,decc,1),add(decc,i+n,0);
 98     }
 99     int ans=0;
100     while(bfs()) ans+=dfs(src,INF);
101     for(int i=1;i<=n;++i) 
102       if(!vis[i]) {
103           vis[i]=true;
104           printf("%d ",i);
105           Print_Road(i);
106           printf("
");
107       }
108     printf("%d
",n-ans);
109     return 0;
110 }
111 
112 int sb=hh();
113 int main() {;}

代码

作者：乌鸦坐飞机
出处：http://www.cnblogs.com/whistle13326/
新的风暴已经出现怎么能够停止不前穿越时空竭尽全力我会来到你身边微笑面对危险梦想成真不会遥远鼓起勇气坚定向前奇迹一定会出现