hdu 1151 Air Raid 二分图匹配

发布时间:2016-12-6 18:15:33 编辑: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题 诡异的楼梯

相关文章

相关评论