首页 > 代码库 > COGS728. [网络流24题] 最小路径覆盖问题
COGS728. [网络流24题] 最小路径覆盖问题
算法实现题8-3 最小路径覆盖问题（习题8-13）
´问题描述：
给定有向图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.txt
11 121 21 31 42 53 64 75 86 97 108 119 1110 11
输出文件示例
output.txt
1 4 7 10 112 5 83 6 93
数据范围：
1<=n<=150,1<=m<=6000
二分图匹配裸题，题面里都写了做法了
记录方案的话，多加个DFS看哪条弧被流过了就行
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 const int INF=1e9; 10 const int mxn=20020; 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15 return x*f; 16 } 17 struct edge{ 18 int v,nxt,f; 19 }e[mxn*50]; 20 int hd[mxn],mct=1; 21 void add_edge(int u,int v,int w){ 22 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=w;hd[u]=mct;return; 23 } 24 void insert(int u,int v,int c){ 25 add_edge(u,v,c);add_edge(v,u,0);return; 26 } 27 int n,m,S,T; 28 int d[mxn]; 29 bool BFS(){ 30 queue<int>q; 31 memset(d,0,sizeof d); 32 q.push(S); 33 d[S]=1; 34 while(!q.empty()){ 35 int u=q.front();q.pop(); 36 for(int i=hd[u];i;i=e[i].nxt){ 37 int v=e[i].v; 38 if(!d[v] && e[i].f){ 39 d[v]=d[u]+1; 40 q.push(v); 41 } 42 } 43 } 44 return d[T]; 45 } 46 int DFS(int u,int lim){ 47 if(u==T)return lim; 48 int f=0,tmp; 49 for(int i=hd[u];i;i=e[i].nxt){ 50 int v=e[i].v; 51 if(d[v]==d[u]+1 && e[i].f && (tmp=DFS(v,min(lim,e[i].f)))){ 52 f+=tmp;lim-=tmp; 53 e[i].f-=tmp; 54 e[i^1].f+=tmp; 55 if(!lim)return f; 56 } 57 } 58 d[u]=0; 59 return f; 60 } 61 int Dinic(){ 62 int res=0; 63 while(BFS())res+=DFS(S,INF); 64 return res; 65 } 66 int a[mxn],cnt=0; 67 bool vis[mxn]; 68 void Search(int u){ 69 vis[u]=1; 70 a[++cnt]=u; 71 for(int i=hd[u];i;i=e[i].nxt){ 72 int v=e[i].v; 73 if(v==S || v==T)continue; 74 if(!e[i].f && !vis[v]) 75 Search(v-n); 76 } 77 } 78 int main(){ 79 freopen("path3.in","r",stdin); 80 freopen("path3.out","w",stdout); 81 int i,j; 82 n=read();m=read(); 83 S=0;T=n+n+1; 84 for(i=1;i<=n;i++){ 85 insert(S,i,1); 86 insert(i+n,T,1); 87 } 88 int u,v; 89 for(i=1;i<=m;i++){ 90 u=read();v=read(); 91 insert(u,v+n,1); 92 } 93 int ans=n-Dinic(); 94 for(i=1;i<=n;i++){ 95 if(vis[i])continue; 96 cnt=0; 97 Search(i); 98 for(j=1;j<=cnt;j++) 99 printf("%d ",a[j]);100 printf("\n");101 }102 printf("%d\n",ans);103 return 0;104 }
COGS728. [网络流24题] 最小路径覆盖问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。