首页 > 代码库 > 二分图最大匹配 (hdu1281、1528)
二分图最大匹配 (hdu1281、1528)
(hdu1281)棋盘游戏
题意:棋盘中一些格子可以放棋子,但要求棋子不能同行也不能同列。有一些格子若不放棋子,则最大匹配数目减少,则这个格子就是“重要点”。
二分图的匹配:给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配。
#include"stdio.h" #include"string.h" #include"stdlib.h" #include"algorithm" using namespace std; #define N 105 int g[N][N]; int mark[N],link[N],n,m; int find(int k) { int i; for(i=1;i<=m;i++) { if(g[k][i]&&!mark[i]) { mark[i]=1; if(link[i]==-1||find(link[i])) { link[i]=k; return 1; } } } return 0; } int main() { int i,j,u,v,k,T=1; while(scanf("%d%d%d",&n,&m,&k)!=-1) { memset(link,-1,sizeof(link)); memset(g,0,sizeof(g)); while(k--) { scanf("%d%d",&u,&v); g[u][v]=1; } int ans=0,cnt=0; for(i=1;i<=n;i++) { memset(mark,0,sizeof(mark)); ans+=find(i); } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(g[i][j]) { g[i][j]=0; memset(link,-1,sizeof(link)); int t=0; for(k=1;k<=n;k++) { memset(mark,0,sizeof(mark)); t+=find(k); } g[i][j]=1; if(t<ans) cnt++; } } } printf("Board %d have %d important blanks for %d chessmen.\n",T++,cnt,ans); } return 0; }
(hdu1528)Card Game Cheater
题意:相当于田忌赛马的游戏,只不过换成扑克牌。比较点数大小,点数相同按花色分大小,红桃》黑桃》方块》梅花。
思路:把每张牌和一个数字映射起来,使得映射后的大小和牌中一样。然后建图,把 Eve的牌大于Adam的牌建一条边。
然后,求出最大匹配就OK了。
#include"stdio.h" #include"string.h" #include"stdlib.h" #define N 60 int a[N],b[N],g[N][N]; int mark[N],link[N]; int getch(char*s) //把牌数转化为数字 { int t; switch(s[0]) { case 'T':t=9;break; case 'J':t=10;break; case 'Q':t=11;break; case 'K':t=12;break; case 'A':t=13;break; default :t=s[0]-'0'-1;break; } t*=4; if(s[1]=='S') t-=1; else if(s[1]=='D') t-=2; else if(s[1]=='C') t-=3; //printf("%d\n",t); return t; } int find(int k) //匈牙利算法求最大匹配数目 { int i; for(i=1;i<N;i++) { if(g[k][i]&&!mark[i]) { mark[i]=1; if(link[i]==-1||find(link[i])) { link[i]=k; return 1; } } } return 0; } int main() { int i,j,t,n,n1,n2,T; char s[5]; scanf("%d",&T); while(T--) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(g,0,sizeof(g)); scanf("%d",&n); n1=n2=0; for(i=0;i<n;i++) { scanf("%s",s); t=getch(s); a[n1++]=t; } for(i=0;i<n;i++) { scanf("%s",s); t=getch(s); b[n2++]=t; } for(i=0;i<n1;i++) //建图 { for(j=0;j<n2;j++) { if(a[i]<b[j]) g[b[j]][a[i]]=1; } } int ans=0; memset(link,-1,sizeof(link)); for(i=1;i<N;i++) { memset(mark,0,sizeof(mark)); ans+=find(i); } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。