hdu 3722 Card Game 二分图的最大权匹配

题目可以转化为2个集合，x集合和y集合，其中的元素是1-n个字符串。

首先预处理点与点的边权，然后直接用二分图的最大权匹配模板。

#include<stdio.h>

#include<string.h>

#define N 210

#define inf 0x3fffffff

int map[N][N],match[N],lx[N],ly[N],sx[N],sy[N],d[N],n;

int find(int x)

{

    sx[x]=1;

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

    {

        if(sy[i]==1)continue;

        int temp=lx[x]+ly[i]-map[x][i];

        if(temp==0)

        {

            sy[i]=1;

            if(match[i]==-1||find(match[i])==1)

            {

                match[i]=x;

                return 1;

            }

        }

        else d[i]=d[i]>temp?temp:d[i];

    }

    return 0;

}

int KM()

{

    int i,j,k,sum,min;

    memset(match,-1,sizeof(match));

    memset(ly,0,sizeof(ly));

    for(i=0;i<n;i++)

    {

        lx[i]=map[i][0];

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

            if(map[i][j]>lx[i])

                lx[i]=map[i][j];

    }

    for(i=0;i<n;i++)

    {

        for(j=0;j<n;j++)

            d[j]=inf;

        while(1)

        {

            memset(sx,0,sizeof(sx));

            memset(sy,0,sizeof(sy));

            if(find(i)==1)break;

            min=inf;

            for(k=0;k<n;k++)

                if(sy[k]==0&&min>d[k])

                    min=d[k];

                for(j=0;j<n;j++)

                {

                    if(sx[j]==1)lx[j]-=min;

                    if(sy[j]==1)ly[j]+=min;

                }

        }

    }

    sum=0;

    for(i=0;i<n;i++)

        sum+=map[match[i]][i];

    return sum;

}

int main()

{

    int i,j,k,sum,p;

    char str[201][1001];

    while(scanf("%d",&n)!=-1)

    {

        for(i=0;i<n;i++)

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

        memset(map,0,sizeof(map));

        for(i=0;i<n;i++)

            for(j=0;j<n;j++)

            {

                for(p=strlen(str[i])-1,k=0;str[j][k]&&p>=0;p--,k++)

                {

                    if(str[i][p]!=str[j][k])break;

                }

                map[i][j]=k;

            }

            sum=KM();

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

    }

    return 0;

}