hdu3722Card Game(KM最大带权匹配) - c++编程基础

题目大意：给n个字符串，再给一个n的排列：p1,p2....pn。然后将第i个字符串贴到第pi个字符串后面，然后形成一个环。pi的首字符和第i个字符串的末尾字符就相邻，如果这2个字符相等，各自再向内延伸一个位置，知道这个环首尾字符不等为止。延伸的位置为该环的得分（如果pi == i，得分为0），对于每个排列，有n个这样的环，求得分和最大为多少。

题目分析：最大带权匹配！！以为是个字符串的题目，就没仔细看。。。

建图直接跑模版。。。

详情请见代码：

#include   
#include  
#include  
using namespace std;  
const int N = 205;  
const int M = 1005;  
const int inf = 0x3f3f3f3f;  
char s[N][M];  
int n;  
int lx[N],ly[N],w[N][N];  
bool cx[N],cy[N];  
int match[N];  
int slack;  
int getw(int x,int y)  
{  
    int i,j;  
    i = strlen(s[x]) - 1;  
    j = 0;  
    int lenj = strlen(s[y]) - 1;  
    int ret = 0;  
    while(i >= 0 && j <= lenj && s[x][i] == s[y][j])  
        i --,j ++,ret ++;  
    return ret;  
}  
void predeal()  
{  
    int i,j;  
    for(i = 1;i <= n;i ++)  
    {  
        for(j = 1;j <= n;j ++)  
            if(i == j)  
                w[i][j] = 0;  
            else  
                w[i][j] = getw(i,j);  
    }  
}  
bool path(int u)  
{  
    cx[u] = true;  
    for(int v = 1;v <= n;v ++)  
    {  
        if(cy[v] == false)  
        {  
            int t = lx[u] + ly[v] - w[u][v];  
            if(t)  
            {  
                if(slack >




 t)  
                    slack = t;  
            }  
            else  
            {  
                cy[v] = true;  
                if(match[v] == -1 || path(match[v]))  
                {  
                    match[v] = u;  
                    return true;  
                }  
            }  
        }  
    }  
    return false;  
}  
void KM()  
{  
    int ans = 0;  
    int i,j;  
    for(i = 1;i <= n;i ++)  
    {  
        lx[i] = -inf;  
        ly[i] = 0;  
        for(j = 1;j <= n;j ++)  
            if(lx[i] < w[i][j])  
                lx[i] = w[i][j];  
    }  
    memset(match,-1,sizeof(match));  
    for(i = 1;i <= n;i ++)  
    {  
        while(1)  
        {  
            memset(cx,false,sizeof(cx));  
            memset(cy,false,sizeof(cy));  
            slack = inf;  
            if(path(i))  
                break;  
            for(j = 1;j <= n;j ++)  
            {  
                if(cx[j])  
                    lx[j] -= slack;  
                if(cy[j])  
                    ly[j] += slack;  
            }  
        }  
    }  
    for(i = 1;i <= n;i ++)  
        ans += w[match[i]][i];  
    printf("%d\n",ans);  
}  
int main()  
{  
    while(scanf("%d",&n) != EOF)  
    {  
        for(int i = 1;i <= n;i ++)  
            scanf("%s",s[i]);  
        predeal();  
        KM();  
    }  
    return 0;  
}