首页 > 代码库 > 洛谷 P2764 LibreOJ 6002 最小路径覆盖问题
洛谷 P2764 LibreOJ 6002 最小路径覆盖问题
题目描述
«问题描述：
给定有向图G=(V,E)。设P 是G 的一个简单路（顶点不相交）的集合。如果V 中每个顶点恰好在P 的一条路上，则称P是G 的一个路径覆盖。P 中路径可以从V 的任何一个顶点开始，长度也是任意的，特别地，可以为0。G 的最小路径覆盖是G 的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图G 的最小路径覆盖。提示：设V={1，2，.... ，n}，构造网络G1=(V1,E1)如下：
每条边的容量均为1。求网络G1的（ 0 x , 0 y ）最大流。
«编程任务：
对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。
输入输出格式
输入格式：
件第1 行有2个正整数n和m。n是给定有向无环图G 的顶点数，m是G 的边数。接下来的m行，每行有2 个正整数i和j，表示一条有向边(i,j)。
输出格式：
从第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
说明
1<=n<=150,1<=m<=6000
吐槽
这题洛谷居然没有SPJ，大家来这里交吧。要在洛谷上AC就必须像造数据的人那样——用链式前向星反着加边，然后跑dinic。我的匈牙利明明能得出一个最优解，洛谷就是给我爆零，大坏蛋。下面的代码能出解不能在洛谷AC，大家别想复制了。因为一些事，心情不爽，我也不太想在洛谷上交dinic了，抄了个题解混一波通过数。
解题思路
裸题。u到v有连边，那么就在二分图里把男u号与女v号牵线，然后跑二分图最大匹配，得到匹配数k，答案最后那行就是$n-k$了。至于前面输出路径，直接顺着二分图走即可，我感觉我的这部分代码挺好懂的(逃)
我的源代码
#include<vector>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m;struct men{ int w;//对象 vector<int> lover;}man[156];int woman[156]={0};inline void add(int u,int v){ man[u].lover.push_back(v);}bool vis[156];bool dfs(int u){ int sz=man[u].lover.size(); for(int i=0;i<sz;i++) { int v=man[u].lover[i]; if(vis[v])continue; vis[v]=1; if(!woman[v]||dfs(woman[v])) { woman[v]=u; man[u].w=v; return 1; } } return 0;}void print(int i){ if(i==0||vis[i]) { printf("\n"); return; } vis[i]=1; printf("%d ",i); print(man[i].w);}int main(){ scanf("%d%d",&n,&m); memset(man,0,sizeof(man)); for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),add(u,v); int ans=0; for(int i=1;i<=n;i++) reverse(man[i].lover.begin(),man[i].lover.end()); for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { if(!vis[i]) print(i); } printf("%d\n",n-ans); return 0;}
洛谷题解代码
#include <stdio.h>#include <cstring>#include <queue>#define maxn 20000#define fill(x,y) memset(x,y,sizeof(x))#define min(x,y) x<y?x:y#define INF 0x7f7f7f7fusing namespace std;struct edge{int y,w,rev,next;}e[maxn];int ls[maxn],n,m,maxE=0,vis[maxn],state[maxn];int add(int x,int y,int w)//将边加入{ e[++maxE]=(edge){y,w,maxE+1,ls[x]}; ls[x]=maxE; e[++maxE]=(edge){x,0,maxE-1,ls[y]}; ls[y]=maxE; return 0;}int bfs(int x)//暴力搜索{ queue <int> t; t.push(x); fill(state,63); state[x]=0; while (!t.empty()) { int tt=t.front();t.pop(); for (int i=ls[tt];i;i=e[i].next) { if (e[i].w>0&&state[tt]+1<state[e[i].y]) { state[e[i].y]=state[tt]+1; t.push(e[i].y); if (e[i].y==n+n+1) return true; } } } return false;}int find(int x,int mn)//dinic{ if (x==n+n+1) return mn; for (int i=ls[x];i;i=e[i].next) if (state[x]+1==state[e[i].y]&&e[i].w>0) { int d=find(e[i].y,min(mn,e[i].w)); if (d>0) { e[i].w-=d; e[e[i].rev].w+=d; vis[x]=e[i].y;//记录路径 return d; } } return 0;}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y+n,1); } for (int i=1;i<=n;i++)//连边 { add(0,i,1); add(n+i,n+n+1,1); } int ans=0; while (bfs(0)) { int d=find(0,INF);//最大流 ans+=d; } for (int i=1;i<=n;i++) { if (vis[i]!=0)//输出路径 { int t=i; do { if (t>n) t-=n; printf("%d ",t); int x=vis[t]; vis[t]=0; t=x; } while (t!=0); printf("\n"); } } printf("%d\n",n-ans);//最小路径覆盖=总点数-最大匹配 return 0;}
洛谷 P2764 LibreOJ 6002 最小路径覆盖问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。