首页 > 代码库 > 【二分图匹配入门专题1】L - Card Game hdu 3722【km算法】

【二分图匹配入门专题1】L - Card Game hdu 3722【km算法】

2024-11-27 19:40:02   203人阅读

Jimmy invents an interesting card game. There are N cards, each of which contains a string Si. Jimmy wants to stick them into several circles, and each card belongs to one circle exactly. When sticking two cards, Jimmy will get a score. The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card. For example, if Jimmy sticks the card S1 containing "abcd" in front of the card S2 containing "dcab", the score is 2. And if Jimmy sticks S2 in front of S1, the score is 0. The card can also stick to itself to form a self-circle, whose score is 0. 

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. 

Given the information of all the cards, please help Jimmy find the best possible score. 

InputThere are several test cases. The first line of each test case contains an integer N (1 <= N <= 200). Each of the next N lines contains a string Si. You can assume the strings contain alphabets (‘a‘-‘z‘, ‘A‘-‘Z‘) only, and the length of every string is no more than 1000. 

OutputOutput one line for each test case, indicating the corresponding answer.Sample Input

3
ab
bcc
ccb
1
abcd

Sample Output

6
0
题意：给你n个字符串，n个字符串中两个字符串相连的权值是串1逆置后和串2的最长公共前缀，自身和自身相连的权值为0，问输出最大完美匹配值。
思路：将串1（1~n）从后往前和串2（1~n）进行匹配，匹配值存入两串相连的边（实现：用两个for进行循环匹配），之后就是km算法啦~~
我不知道自己哪里来的想法在读入结束条件加一个n!=0，结果一直超时，我各种优化还是超时，到了饭点才发现自己输入的问题，真是一个浪费时间的bug

 

#include<stdio.h>
#include<string.h>
#define N 210
#define M 1110
#define INF 0x3f3f3f3f

int w[N][N],lx[N],ly[N];
int visx[N],visy[N],linker[N],slack[N];
int n,ans,nx,ny;
char e[N][M];

void Getmap()//建图 
{
    int i,j,x,y,count,l;
    for(x = 1; x <= n; x ++)
    {
        for(y = 1; y <= n; y ++)
        {
            if(x == y)
                w[x][y] = 0;
            else
            {
                l = strlen(e[x]+1);
                count = 0;
                for(i = l,j = 1;i > 0&&e[y][j]!=‘\0‘;i--,j++)
                {
                    if(e[x][i] == e[y][j])
                        count++;
                    else
                        break;
                }
                w[x][y] = count;
            }
        }
    }
    return;    
}

int dfs(int x)//寻找增广路 
{
    int y,tmp;
    visx[x] = 1;
    for(y = 1; y <= ny; y ++)
    {
        if(!visy[y])
        {
            tmp = lx[x] + ly[y] - w[x][y];
            if(!tmp)
            {
                visy[y] = 1;
                if(linker[y] == -1||dfs(linker[y]))
                {
                    linker[y] = x;
                    return 1;
                }
            }
            else if(slack[y] > tmp)
                slack[y] = tmp;
        }
    }
    return 0;
}
int KM()//km算法 
{
    int x,y,i,j,sum,d;
    memset(linker,-1,sizeof(linker));
    memset(ly,0,sizeof(ly));
    
    for(x = 1; x <= nx; x ++)
        for(y = 1,lx[x] = -INF; y <= ny; y ++)
            if(lx[x] < w[x][y])
                lx[x] = w[x][y];
                
    for(x = 1; x <= nx; x ++)
    {
        for(i = 1; i <= ny; i ++)
            slack[i] = INF;
        while(1)
        {
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            d = INF;
            if(dfs(x))
                break;
            for(y = 1; y <= ny; y ++)
                if(!visy[y]&&d > slack[y])
                    d = slack[y];
            for(i = 1; i <= nx; i ++)
                if(visx[i])
                    lx[i] -= d;
                    
            for(i = 1; i <= ny; i ++)
                if(visy[i])
                    ly[i] += d;
                else
                    slack[i]-=d;
        }
    }
    sum = 0;
    for(i = 1; i <= ny; i ++)
        if(linker[i]!=-1)
            sum += w[linker[i]][i];
    return sum;
}

int main()
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
        getchar();
        nx = ny = n;
        for(i = 1; i <= n; i ++)
            scanf("%s",e[i]+1);
        Getmap();//建图 
        ans = KM();//km算法 
        printf("%d\n",ans);
    }
    return 0;
}

 

【二分图匹配入门专题1】L - Card Game hdu 3722【km算法】


联系
我们