HDU - 1962 二分图最大匹配模板（扑克牌得分最大）

题意：

直接说数据，第一行给定几组数据，每一组数据的第一行是两个人扑克牌分别的数量，第一行是亚当的扑克牌，第二行是夏娃的扑克牌，每一个扑克牌的大小用两个字符来表示，第一个表示是几号扑克牌，第二个表示扑克牌的花色（题中有给）

思路：

这是二分图最大匹配的模板题，二酚涂最大匹配需要用一个数组来记录匹配的路径。这里面是数组a，首先需要判断这两行的扑克牌互相之间的大小关系。然后以亚当手里的扑克牌为基准，枚举每一个扑克牌，如果对应的夏娃的扑克牌没有被其他扑克牌打败，或者将这个扑克牌打败的亚当的扑克牌有一条增广路，也就是说可以去打败其它的扑克牌。给这个扑克牌让位置，然后记录路径。

看代码：（比较好理解）

#include<stdio.h>

#include<map>

#include<string.h>

using namespace std;

char ya[50][3],xa[50][3];

int e[50][50];

map<char,int>M;

char c='C',d='D',s='S',h='H';

int pan(int i,int j)

{

    if(ya[j][0]==xa[i][0])

    {

        if(M[xa[i][1]]>M[ya[j][1]])

            return 1;

    }

    else

    {

        if(M[xa[i][0]]>M[ya[j][0]])

            return 1;

    }

    return 0;

}

int n,a[110],book[110];

int dfs(int u)//第二行

{

    for(int i=1; i<=n; i++)

    {

        if(book[i]==0&&e[u][i])

        {

            book[i]=1;

            if(dfs(a[i])||a[i]==0)

            {

                a[i]=u;

                return 1;

            }

        }

    }

    return  0;

}

int main()

{

    M['A']=14,M['2']=2,M['3']=3,M['4']=4,M['5']=5;

    M['6']=6,M['7']=7,M['8']=8,M['9']=9,M['T']=10;

    M['J']=11, M['Q']=12, M['K']=13;

    M[c]=1,M[d]=2,M[s]=3,M[h]=4;

    int t;

    scanf("%d",&t);

    while(t--)

    {

        memset(e,0,sizeof(e));

        memset(a,0,sizeof(a));//路径数组

        scanf("%d",&n);

        for(int i=1; i<=n; i++)

            scanf("%s",ya[i]);

        for(int i=1; i<=n; i++)

            scanf("%s",xa[i]);

        //printf("%d ****\n",pan(2,2));//第一个是夏娃，第二个是亚当

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

               if(pan(i,j))

                   e[i][j]=1;

        int sum=0;

        for(int i=1; i<=n; i++)//从夏娃开始 第一列

        {

            memset(book,0,sizeof(book));

            if(dfs(i))//增广路

                sum++;

        }

        printf("%d\n",sum);

    }

    return 0;

}

巴特西

HDU - 1962 二分图最大匹配模板（扑克牌得分最大）

最新文章

热门文章