首页 > 代码库 > [网络流24题] 最小路径覆盖问题
[网络流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：
11 121 21 31 42 53 64 75 86 97 108 119 1110 11
输出样例#1：
1 4 7 10 112 5 83 6 93
这篇博客讲的好 我就不写了
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("\n");107 }108 printf("%d\n",n-ans);109 return 0;110 }111 112 int sb=hh();113 int main() {;}
[网络流24题] 最小路径覆盖问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。