[看毛片算法][KM]zoj 3615：Choir II

大致题意：
? ? 有n个男生，m个女生，每个人用一句话描述其他的异性。对与第i个人和第j个异性，其好感值为其姓名第一次出现的位置和出现次数的乘积。现在要匹配这些人，使得总的好感值之和最大，求这个值。

?

大致思路：

? ? kmp算法加km。km模版有点问题，n不能小于m，所以加了一句n=m=max(n,m)糊弄过去了。

?

#include<iostream>#include<cstring>#include<cstdio>using namespace std;char name[300][50],str[300][20000];const int nMax=300;const int mMax=20005;const int inf=1<<30;int map[300][300];int n,m;//char text[mMax],pat[nMax];int lent,lenp,next[nMax];void get_next(char *pat){    int i,j=-1;    next[0]=-1;    for(i=1;i<=lenp;i++){     //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符        while(j>-1&&pat[j+1]!=pat[i])j=next[j];        if(pat[j+1]==pat[i])j++;        next[i]=j;    }}int KMP(char *pat,char *text,int &pos){    int ans=0,i=0,j=-1; //   get_next();    bool flag=1;    for(i=0;i<lent;i++){        while(j!=-1&&pat[j+1]!=text[i]){            j=next[j];        }        if(pat[j+1]==text[i])j=j+1;        if(j==lenp-1)        {            if(flag)            {                pos=i;                flag=0;            }            ans++;  //找到一个匹配        }    }    return ans;}int solve(int a,int b){    int i,j,c,fp;//    for(i=0;i<strlen(str[a]);i++)//    {//        text[i]=str[a][i];//    }//    text[strlen(str[a])]='\0';//    for(i=0;i<strlen(name[b]);i++)//    {//        pat[i]=name[b][i];//    }//    pat[strlen(name[b])]='\0';    lenp=strlen(name[b]);    lent=strlen(str[a]);    get_next(name[b]);    c=KMP(name[b],str[a],fp);    if(c==0)fp=1;    else{        fp=fp-strlen(name[b]);        fp+=2;    }   // cout<<a<<" "<<b<<" "<<fp<<" "<<c<<endl;    return (fp)*c;}int lx[nMax],ly[nMax];int mapch[nMax];int stack[nMax];bool sy[nMax],sx[nMax];int e,cnt;int find (int u){    int v,t;    sx[u]=1;    for(v=1;v<=m;v++){        if(sy[v]) continue;        t=lx[u]+ly[v]-map[u][v];        if(t==0){            sy[v]=1;            if(mapch[v]==-1||find(mapch[v])){                mapch[v]=u;                return 1;            }        }        else if(t<stack[v]) stack[v]=t;    }    return 0;}int KM(){    int i,j,k,d,sum=0;    cnt=0;    for(i=1;i<=m;i++)        ly[i]=0;    memset(mapch,-1,sizeof(mapch));    for(i=1;i<=n;i++){        lx[i]=-inf;        for(j=1;j<=m;j++)            if(map[i][j]>lx[i])                lx[i]=map[i][j];    }    for(i=1;i<=n;i++){        for(j=1;j<=m;j++)            stack[j]=inf;        while(1){            for(k=1;k<=m;k++) sy[k]=0;            for(k=1;k<=n;k++) sx[k]=0;            if(find(i)) break;            d=inf;            for(k=1;k<=m;k++)                if(!sy[k]&&stack[k]<d)                    d=stack[k];            for(k=1;k<=n;k++)                if(sx[k]) lx[k]-=d;            for(k=1;k<=m;k++)                if(sy[k]) ly[k]+=d;                else stack[k]-=d;        }    }    for(i=1;i<=m;i++)        if(mapch[i]!=-1&&map[mapch[i]][i]!=-inf){            sum+=map[mapch[i]][i];        }    return sum;}int main(){    int i,j;    while(cin>>n>>m)    {        memset(map,0,sizeof(map));       for(i=1;i<=m+n;i++)       {           cin>>name[i];           getchar();           name[i][strlen(name[i])-1]='\0';           gets(str[i]);       }       for(i=1;i<=n;i++)           for(j=1;j<=m;j++)           {               map[i][j]+=solve(i,j+n);               map[i][j]+=solve(j+n,i);           }        n=m=max(n,m);        cout<<KM()<<endl;    }    return 0;}