Card Game Cheater HDU1528

二分图最大匹配问题 

扑克题还是用map比较方便 

#include<bits/stdc++.h>
using namespace std;
#define MAXI 52
int yd[MAXI][2];
int xw[MAXI][2];
int used[MAXI];
int vis[MAXI];
int n,m;

map<char,int>mm;

bool judge(int a,int b)
{
   if( mm[xw[a][0]]>mm[ yd[b][0] ] )
    return true;
   else if(mm[xw[a][0]]==mm[ yd[b][0] ])
    return mm[xw[a][1]]>mm[ yd[b][1] ];
   else
    return false;
}

bool dfs(int  x)//x指夏娃数组下标
{
    for(int j=1;j<=n;j++)//j是亚当的
    {
        if(judge(x,j)&&!used[j])
        {
            used[j]=1;
            if(!vis[j]||dfs(vis[j]) )
              {
                  vis[j]=x;
                  return true;
              }
        }
    }
    return false;
}

int find1(void)
{    int ans=0;
     memset(vis,0,sizeof(vis));
     for(int i=1;i<=n;i++)//这里的i指的是夏娃的
       {
           memset(used,0,sizeof(used));
           if(dfs(i))ans++;
       }
       return ans;
}

int main()
{
  int cas;
  cin>>cas;
  for(char i='2';i<='9';i++)
      mm[i]=i-'0';
  mm['T']=10;
  mm['J']=11;
  mm['Q']=12;
  mm['K']=13;
  mm['A']=14;
  mm['C']=1;
  mm['D']=2;
  mm['S']=3;
  mm['H']=4;
  int first=1;
  while(cas--)
  {
     scanf("%d",&n);
     char s[5];
     for(int i=1;i<=n;i++)
     {
         scanf("%s",s);
         yd[i][0]=s[0];
         yd[i][1]=s[1];
     }
      for(int i=1;i<=n;i++)
      {
          scanf("%s",s);
          xw[i][0]=s[0];
          xw[i][1]=s[1];
      }
      printf("%d\n",find1());
  }
  return 0;
}

 

上一篇:SQL面试题练习


下一篇:JavaScript中this的问题