学步园

一道简单的二分图的最大匹配。。

关键的核心就是会建图转化。。。

用一个change函数转化之后比较两副牌的大小。

如果后者比前者大。。符合题意，则视为一条路径。。

最后求此图的最大匹配即可。

此题最后WA了一次，，原因在于将A牌视为最小牌了。。。

改了之后AC。

代码如下：

#include<stdio.h>
#include<string.h>
char card[30][5];
char s[5];
int map[30][30];
int vis[30];
int link[30];
int k;
int find(int a)
{
    for(int i=1; i<=k; i++)
    {
        if(!vis[i]&&map[a][i])
        {
            vis[i]=1;
            if(link[i]==-1||find(link[i]))
            {
                link[i]=a;
                return 1;
            }
        }
    }
    return 0;
}
int sum()
{
    int res=0;
    memset(link,-1,sizeof(link));
    for(int i=1; i<=k; i++)
    {
        memset(vis,0,sizeof(vis));
        if(find(i))
            res++;
    }
    return res;
}
void change(char a[])
{
    if(a[0]=='A')
        a[0]='0'+14;
    else if(a[0]=='T')
        a[0]='0'+10;
    else if(a[0]=='J')
        a[0]='0'+11;
    else if(a[0]=='Q')
        a[0]='0'+12;
    else if(a[0]=='K')
        a[0]='0'+13;
    if(a[1]=='H')
    a[1]='4';
    else if(a[1]=='S')
    a[1]='3';
    else if(a[1]=='D')
    a[1]='2';
    else if(a[1]=='C')
    a[1]='1';
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(map,0,sizeof(map));
        memset(card,'\0',sizeof(card));
        scanf("%d",&k);
        for(int i=1; i<=k; i++)
            scanf("%*c%s",card[i]);
        //printf("**\n");
        for(int i=1; i<=k; i++)
        {
            scanf("%*c%s",s);
            for(int j=1; j<=k; j++)
            {
                change(card[j]);
                change(s);
                if(s[0]>card[j][0])
                map[i][j]=1;
                else if(s[0]==card[j][0]&&s[1]>card[j][1])
                map[i][j]=1;
                //printf("**%d\n",map[i][j]);
            }
        }
        int res=sum();
        printf("%d\n",res);
    }
    return 0;
}