首页 > 代码库 > 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