首页 > 代码库 > 【网络流#6】POJ 3041 Asteroids 二分图最大匹配 - 《挑战程序设计竞赛》例题
【网络流#6】POJ 3041 Asteroids 二分图最大匹配 - 《挑战程序设计竞赛》例题
学习网络流中ing...作为初学者练习是不可少的~~~构图方法因为书上很详细了，所以就简单说一说
把光束作为图的顶点，小行星当做连接顶点的边，建图，由于 最小顶点覆盖 等于 二分图最大匹配 ，因此求二分图最大匹配即可。
邻接矩阵，DFS寻找增广路，匈牙利算法
邻接矩阵：复杂度O(n^3)
如果使用邻接表：复杂度O(n*m)
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)using namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,match[505],g[505][505],r,c;bool flag,vis[505];bool hungary(int u)//从u开始寻找增广路 { for (int i=1;i<=n;i++) { if (g[u][i]&&!vis[i])//G数组存储邻接矩阵，match[i]表示当前结点i匹配的结点 { vis[i]=1; if (match[i]==0||hungary(match[i])) return match[i]=u; } } return 0;}int main(){ scanf("%d%d",&n,&k); for (i=1;i<=k;i++) { scanf("%d%d",&r,&c); g[r][c]=1; } ans=0; /*匈牙利算法过程 - 寻找增广路*/ for (i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if (hungary(i)) ans++; } /*寻找结束*/ printf("%d\n",ans); return 0;}
【网络流#6】POJ 3041 Asteroids 二分图最大匹配 - 《挑战程序设计竞赛》例题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。