首页 > 代码库 > 网络流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
有点逆向思考的感觉
最差情况所有的点都是一条路径
两个点连起来的话就少一条路径一个点
拆成入点X和出点Y，构成二分图，ans=n-最大匹配数
关于打印：
最大流中流量为1的边就是匹配边，先处理to[i],从ind[i]==0的点开始打印
//// main.cpp// wang24.3//// Created by Candy on 29/11/2016.// Copyright © 2016 Candy. All rights reserved.//#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=2005,M=1e6,INF=1e9;int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,m,s,t,u,v;struct edge{ int v,ne,c,f;}e[M<<1];int cnt,h[N];inline void ins(int u,int v,int c){ cnt++; e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt;}int vis[N],d[N],q[N],head=1,tail=1;bool bfs(){ memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); head=tail=1; q[tail++]=s;d[s]=0;vis[s]=1; while(head!=tail){ int u=q[head++]; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!vis[v]&&e[i].c>e[i].f){ vis[v]=1;d[v]=d[u]+1; q[tail++]=v; if(v==t) return true; } } } return false;}int cur[N];int dfs(int u,int a){ if(u==t||a==0) return a; int flow=0,f; for(int &i=cur[u];i;i=e[i].ne){ int v=e[i].v; if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){ flow+=f; e[i].f+=f; e[((i-1)^1)+1].f-=f; a-=f; if(a==0) break; } } return flow;}int dinic(){ int flow=0; while(bfs()){ for(int i=s;i<=t;i++) cur[i]=h[i]; flow+=dfs(s,INF); } return flow;}int to[N],ind[N];void print(){ for(int u=1;u<=n;u++) for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(e[i].c==1&&e[i].f==1) to[u]=v-n,ind[v-n]++; } for(int i=1;i<=n;i++) if(!ind[i]){ int u=i; while(u!=0) printf("%d ",u),u=to[u]; putchar(‘\n‘); }}int main(int argc, const char * argv[]) { n=read();m=read();s=0;t=n+n+1; for(int i=1;i<=m;i++){ u=read();v=read(); ins(u,n+v,1); } for(int i=1;i<=n;i++) ins(s,i,1),ins(n+i,t,1); int ans=n-dinic(); print(); printf("%d",ans); return 0;}
网络流24题 最小路径覆盖问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。