博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[网络流24题]最小路径覆盖问题
阅读量:5115 次
发布时间:2019-06-13

本文共 1248 字,大约阅读时间需要 4 分钟。

最小路径覆盖模板题

#include
#include
#include
#include
#define maxn 155#define maxm 6005using namespace std;int n,m;struct edge{ int from; int to; int next;}E[maxm];int sz=0;int head[maxn];void add_edge(int u,int v){ sz++; E[sz].from=u; E[sz].to=v; E[sz].next=head[u]; head[u]=sz;}int vis[maxn*2];int match[maxn*2];int dfs(int x){ for(int i=head[x];i;i=E[i].next){ int y=E[i].to; if(!vis[y]){ vis[y]=1; if(!match[y]||dfs(match[y])){ match[y]=x; match[x]=y; return 1; } } } return 0;}void print(int x){ x+=n; do{ x-=n; printf("%d ",x); vis[x]=1; x=match[x]; }while(x!=0); printf("\n"); }int main(){ int x,y; scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d %d",&x,&y); add_edge(x,y+n); } int ans=0; 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);}

转载于:https://www.cnblogs.com/birchtree/p/10314605.html

你可能感兴趣的文章
Java异常(输出[D@139a55问题)
查看>>
鸟哥Linux私房菜笔记(二):正则表达式、shell脚本
查看>>
(linux自学笔记)进程与线程
查看>>
maven打包二进制文件
查看>>
企业做数据缓存是使用Memcached还是选Redis?
查看>>
服务器配置不安全
查看>>
PreparedStatement 与 Statement 的区别
查看>>
象棋人机对弈程序的思想
查看>>
实验一
查看>>
Hamburger Magi 状压dp
查看>>
动软代码生成器 如果有id主键 和没有id主键是不一样的
查看>>
JavaScript实现向右伸出的多级网页菜单
查看>>
[功能改进]Live Writer发博支持“建分类、加标签、写摘要”
查看>>
JavaScript学习笔记
查看>>
ajax防止表单自动提交
查看>>
Fileupload
查看>>
Linux添加用户失败
查看>>
计算广告的相关学习资源
查看>>
CMDB学习之六 --客户端请求测试,服务端api优化
查看>>
java学习笔记_GUI(4)
查看>>