HDU 3722 Card Game(二分图最优匹配)

HDU 3722 Card Game(二分图最优匹配)

http://acm.hdu.edu.cn/showproblem.php?pid=3722

题意:

给出n个字符串,其中任意两个字符串(包括同一字符串)可以进行互相拼接起来,例如s1="abcd"……>s2="dcab",表示将s1拼接在s2后面,所得的值就是将s1反转得"dcba",该字符串与s2同有的前缀为"dc",所以值就是2.现在求解在n个字符串给定的情况下,将这些字符串拼接起来所得到的最大值.

分析:

如果将S[i]连接到S[j]后面能得到x分数,那么就连一条i到j的权值为x的有向边. 最终我们能得到一个有向图. 我们要求的是是否存在不相交的多个有向环正好覆盖了该有向图的N个点且这些环的权值和最小? (其实本题就是HDU1853的修改版,只不过需要我们自己建图而已:http://blog.csdn.net/u013480600/article/details/38760767)

建立二分图:左右点集都是1到n个数字,代表1到n的字符串编号. 如果将S[i]连接到S[j]后面能得到x分数,那么就连一条左i与右j的权值为x的边.

最终用KM算法求得的最优匹配权值就是可能获得的最大分数.(具体二分图实现正确性证明部分请看HDU1853的分析)

注意:本题能存在自环,但是自环的权值恒为0.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
const int maxn=200+10;

struct Max_Match
{
    int n,W[maxn][maxn];
    int Lx[maxn],Ly[maxn];
    bool S[maxn],T[maxn];
    int left[maxn];

    bool match(int i)
    {
        S[i]=true;
        for(int j=1;j<=n;j++)if(Lx[i]+Ly[j]==W[i][j] && !T[j])
        {
            T[j]=true;
            if(left[j]==-1 || match(left[j]))
            {
                left[j]=i;
                return true;
            }
        }
        return false;
    }

    void update()
    {
        int a=1<<30;
        for(int i=1;i<=n;i++)if(S[i])
        for(int j=1;j<=n;j++)if(!T[j])
            a=min(a,Lx[i]+Ly[j]-W[i][j]);
        for(int i=1;i<=n;i++)
        {
            if(S[i]) Lx[i] -=a;
            if(T[i]) Ly[i] +=a;
        }
    }

    int solve(int n)
    {
        this->n=n;
        memset(left,-1,sizeof(left));
        for(int i=1;i<=n;i++)
        {
            Lx[i]=Ly[i]=0;
            for(int j=1;j<=n;j++)
                Lx[i]=max(Lx[i],W[i][j]);
        }

        for(int i=1;i<=n;i++)
        {
            while(true)
            {
                for(int j=1;j<=n;j++) S[j]=T[j]=false;
                if(match(i)) break;
                else update();
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++) ans+= W[left[i]][i];
        return ans;
    }
}KM;

int get_score(string& s1,string& s2)//将s1连到s2后面所能得到的分数
{
    int ans=0;
    for(unsigned int i=0;i<s1.size()&&i<s2.size();i++)
    {
        if(s1[i]==s2[s2.size()-1-i]) ++ans;
        else return ans;
    }
    return ans;
}

int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        string s[maxn];
        for(int i=1;i<=n;i++)
            cin>>s[i];
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            KM.W[i][j]= i==j?0:get_score(s[i],s[j]);//注意:自环权值为0

        printf("%d\n",KM.solve(n));
    }
    return 0;
}