hdu 1151 Air Raid 二分图匹配

发布时间:2017-3-28 8:31:04 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 1151 Air Raid 二分图匹配",主要涉及到hdu 1151 Air Raid 二分图匹配方面的内容,对于hdu 1151 Air Raid 二分图匹配感兴趣的同学可以参考一下。

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define N 130 vector<int> g[N]; bool vis[N]; int linker[N]; bool dfs(int u){ for(int i=0;i<g[u].size();i++){ int v=g[u][i]; if(!vis[v]){ vis[v]=1; if(linker[v]==-1||dfs(linker[v])){ linker[v]=u; return true; } } } return false; } int hungary(int n){ memset(linker,-1,sizeof(linker)); int ans=0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } return ans; } int main(){ int t,n,m; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) g[i].clear(); int r,c; while(m--){ scanf("%d%d",&r,&c); g[r].push_back(c); //g[c].push_back(r); } printf("%d\n",n-hungary(n)); } return 0; } 这题其实质是求有向图图的最小路径覆盖,而最小路径覆盖=顶点数-二分图匹配数 这题需要注意:图是有向图,就是说边是单向的。

上一篇:php文件上传
下一篇:HDU 1180题 诡异的楼梯

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款