题目请戳这里

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

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

建图直接跑模版。。。

详情请见代码：

#include <iostream>

#include<cstdio>

#include<cstring>

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;

}