Hud 1528 Card Game Cheater[二分匹配]

兩兩節點的有聯系的前提就是：Eve的牌大於Adam的牌。

這樣已處理的話就是一個很裸二分圖匹配的問題了。

什麼都不多解釋了，直接代碼。

#include 
#include 
#include 
#include 
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int N=30;
const char number[]={0,'2','3','4','5','6','7','8','9','T','J','Q','K','A'};
const char color[]={'C','D','S','H'};
bool Map[N][N],Vis[N];
int Match[N];
int k;
struct Poker{
    char Number;
    char Color;
}Adam[N],Eve[N];

bool JudgeColor(char a,char b)
{
    int x,y;
    for(int i=0;i<4;i++){
        if(a==color[i]) x=i;
        if(b==color[i]) y=i;
    }
    if(x>y) return true;
    else return false;
}

bool Judge(Poker a,Poker b)
{
//    printf("%c %c\n",a.Number,b.Number);
    int temp1,temp2;
    for(int i=1;i<=13;i++){
        if(a.Number==number[i]) temp1=i;
        if(b.Number==number[i]) temp2=i;
    }
//    printf("%d %d\n",temp1,temp2);
    if(temp1>temp2) return true;
    else if(temp1==temp2){
        if(JudgeColor(a.Color,b.Color)) return true;
        else return false;
    }
    else return false;
}

bool Find_Path(int x)
{
    for(int i=1;i<=k;i++){
        if(Map[x][i]&&!Vis[i])
        {
            Vis[i]=true;
            if(!Match[i]||Find_Path(Match[i]))
            {
                Match[i]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
//    freopen("1.txt","r",stdin);
    int n;
    scanf("%d",&n);
    while(n--)
    {
        CLR(Map,0);CLR(Vis,0);CLR(Match,0);
        scanf("%d",&k);
        //getchar();
        for(int i=1;i<=k;i++)
        cin>>Adam[i].Number>>Adam[i].Color;
        for(int i=1;i<=k;i++)
        cin>>Eve[i].Number>>Eve[i].Color;
        //getchar();
        for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++){
            if(Judge(Eve[i],Adam[j]))
            Map[i][j]=true;
        }
        int ans=0;
        for(int i=1;i<=k;i++)
        {
            if(Find_Path(i))
            ans++;
            CLR(Vis,0);
        }
        printf("%d\n",ans);
    }
    return 0;
}