Card Game(网络流，KM)

                                                                     Card Game

题目链接:Click Here~

题目分析：

     给你n张卡片，每张卡片上都有一串字母，问你如何链接卡片使得最后的得分最多。卡片自己可以连接自己。得分的标准是如果链接两种卡片s1,s2的时候，最终的得分是将s1反转看其跟s2的前缀有多上个相同的字母，有几个相同的字母就表示s1->s2可以得到的分数。

For example, there are 3 cards, whose strings are S1="ab", S2="bcc", S3="ccb". There are 6 possible sticking:
1.  S1->S2, S2->S3, S3->S1, the score is 1+3+0 = 4
2.  S1->S2, S2->S1, S3->S3, the score is 1+0+0 = 1
3.  S1->S3, S3->S1, S2->S2, the score is 0+0+0 = 0
4.  S1->S3, S3->S2, S2->S1, the score is 0+3+0 = 3
5.  S1->S1, S2->S2, S3->S3, the score is 0+0+0 = 0
6.  S1->S1, S2->S3, S3->S2, the score is 0+3+3 = 6
So the best score is 6.

算法分析：

   这是一道2010年的区域赛题，出的很严谨。一开始可能没感觉，但是当你越推敲他的时候发现其给出的条件越多。这题其实就是标准的完全匹配的最大权值问题。因为，题目给出了很多小的暗示，表示肯定可以达到完美匹配。感兴趣的可以自己认真读题。虽然做了几道KM算法题，但是还是对其原理本质很模糊啊。要继续努力，加油！ ^_^

建模分析：

   既然知道了是标准的完全匹配问题了，建图就应该没什么难得了。但是一开始我还是建错了冏。。。后来重复的看代码才发现了错误。一开还以为要拆点，后来发现只要有联系的两个点连线就好了，这其实题目也有给出了说明，就是自己可以链接自己，每两个字符都可以连接。建完图之后，就是KM算法的问题了。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = ~0U >> 2;
const int MAXN = 200 + 5;
int n,graph[MAXN][MAXN];
int slack,Lx[MAXN],Ly[MAXN],Link[MAXN];
bool S[MAXN],T[MAXN];
char str[MAXN][1002];
int Get(char *str1,char *str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int i = len1-1,j = 0;
    while(i>=0&&j<len2){
        if(str1[i]!=str2[j])
            break;
        --i;
        ++j;
    }
    return j;
}
bool Match(int i)
{
    S[i] = true;
    for(int j = 1;j <= n;++j){
      if(!T[j]){     
          int tmp = Lx[i]+Ly[j]-graph[i][j];
          if(tmp==0){     
              T[j] = true;   
              if(Link[j]==-1||Match(Link[j])){
                  Link[j] = i;
                  return true;
              }
          }
          else if(tmp < slack)
               slack = tmp;
      }
    }
    return false;
}
void Update(int d)
{      cout<<"slack == "<<d<<endl;
    for(int i = 1;i <= n;++i){
        if(S[i])
            Lx[i] -= d;
        if(T[i])
            Ly[i] += d;
    }
}
bool EK()
{
    for(int i = 1;i <= n;++i){
        Link[i] = -1;
        Lx[i] = Ly[i] = 0;         
        for(int j = 1;j <= n;++j)
            Lx[i] = max(Lx[i],graph[i][j]);
    }
                                    
    slack = INF;
    for(int i = 1;i <= n;++i){
        for(;;){
            memset(S,0,sizeof(S));
            memset(T,0,sizeof(T));
            if(Match(i))
                break;
            if(slack==INF)
                return false;
            Update(slack);
        }
    }
    return true;
}
int GetAns()
{
    int sum = 0;
    for(int i = 1;i <= n;++i){
        if(Link[i]!=-1){
            sum += graph[Link[i]][i];
        }
    }
    return sum;
}
int main()
{
//    freopen("Input.txt","r",stdin);
//    freopen("Out.txt","w",stdout);

    while(~scanf("%d",&n))
    {
        for(int i = 1;i <= n;++i)
            scanf("%s",str[i]);
        memset(graph,0,sizeof(graph));
        for(int i = 1;i <= n;++i){
            for(int j = i+1;j <= n;++j){
                graph[i][j] = Get(str[i],str[j]);
                graph[j][i] = Get(str[j],str[i]);
            }
        }
        EK();
        printf("%d\n",GetAns());
    }
    return 0;
}

Card Game(网络流，KM),布布扣,bubuko.com

Card Game(网络流，KM)

原文：http://blog.csdn.net/zhongshijunacm/article/details/23601815