[看毛片算法][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;}?