首页 > 代码库 > HDU 5090 Game with Pearls
HDU 5090 Game with Pearls
题目地址
二分图最大匹配,将1-n分为二分图的一边,编号1-n为另一边,当编号1-n中的数字加0或k的整数倍为j(j<=n)的时候将编号i与j相连。
如此,这个二分图中如果最大匹配数为n,则Jerry赢,否则Tom赢。
1 #include<stdio.h> 2 #include<algorithm> 3 using namespace std; 4 const int Nmax=305; 5 int t,n,k,x,ans; 6 int match[Nmax],book[Nmax],map[Nmax][Nmax]; 7 int init() 8 { 9 ans=0;10 for(int i=1;i<=n;i++)11 for(int j=1;j<=n;j++)12 map[i][j]=0;13 for(int i=1;i<=n;i++)14 match[i]=book[i]=0;15 }16 17 int dfs(int u)18 {19 for(int i=1;i<=n;i++)20 {21 if(map[i][u] && !book[i])22 {23 book[i]=1;24 if(!match[i] || dfs(match[i]))25 {26 match[i]=u;27 return 1;28 }29 }30 31 }32 return 0;33 }34 35 int main()36 {37 scanf("%d",&t);38 while(t--)39 {40 scanf("%d%d",&n,&k);41 init();42 for(int i=1;i<=n;i++)43 {44 scanf("%d",&x);45 for(int j=x;j<=n;j+=k)46 map[j][i]=1;47 }48 for(int i=1;i<=n;i++)49 {50 for(int j=1;j<=n;j++) book[j]=0;51 if(dfs(i))52 ans++;53 }54 if(ans==n)55 printf("Jerry\n");56 else57 printf("Tom\n");58 }59 return 0;60 }
HDU 5090 Game with Pearls
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。