好贷网好贷款

HDU-2063-最大匹配

发布时间:2016-12-4 20:19:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU-2063-最大匹配",主要涉及到HDU-2063-最大匹配方面的内容,对于HDU-2063-最大匹配感兴趣的同学可以参考一下。

很经典的一道最大匹配问题,算法主要是考虑冲突间的问题详细解说请看代码 #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define MAX 1005 int map[MAX][MAX],dis[MAX],inq[MAX]; int n,m; int find(int t) { int j; for(j=1;j<=n;j++) { if(!inq[j]&&map[t][j])//如果没有考虑过且存在能够匹配 { inq[j]=1;//标记考虑 if(dis[j]==-1||find(dis[j]))//如果没有匹配过(即没有冲突)||该女生还有能够选择的男生,选择没有冲突的男生 { dis[j]=t;//将他们匹配(注意虽然已经匹配,但上一行的代码中的||还可以对其进行改变 ) return 1; } } } return 0; } int maxn() { int sum,i; sum=0; memset(dis,-1,sizeof(dis)); for(i=1;i<=m;i++) { memset(inq,0,sizeof(inq));//注意每次都要清零 if(find(i))//找到冲突最小的配对 sum++; } return sum; } int main() { int k,i,a,b; while(scanf("%d",&k),k!=0) { cin>>m>>n; memset(map,0,sizeof(map)); for(i=1;i<=k;i++) { cin>>a>>b; map[a][b]=1; } cout<<maxn()<<endl; } return 0; }

上一篇:找回 Mac OS X Lion 10.7中被隐藏的 资源库(Library)
下一篇:关于pyopengl运行时的问题

相关文章

相关评论