[KM算法]hdoj 3722：Card Game

大致题意：

要把n个字符串首尾相连成若干个环，如果把s1接到s2的后面可以得到一定的收获值，这个值等于s2的逆序 和s1的最长相同前缀的长度。求总收获值最大是多少。

大致思路：

看完题就感觉是KM二分图最大全匹配，匹配部分思路和hdu1853类似。感觉字符串部分的复杂度过高，以为有什么牛逼的算法，迟迟不敢下手敲，看了别人题解才发现暴力就行了。

#include<cstdio>#include<iostream>#include<cstring>using namespace std;const int nMax=204;const int mMax=1005;const int inf=1<<29;int map[nMax][nMax];int lx[nMax],ly[nMax];int mapch[nMax];int stack[nMax];bool sy[nMax],sx[nMax];int n,m,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;}char str[nMax][1003];int maxpre(int a,int b){int i,j;int ans=0;int la=strlen(str[a]);int lb=strlen(str[b]);for(i=0,j=lb-1;;){if(i<la&&j>=0&&str[a][i]==str[b][j]){i++;j--;ans++;}else break;}return ans;}int main(){int i,j;while(scanf("%d",&n)!=EOF){m=n;memset(map,0,sizeof(map));for(i=1;i<=n;i++){scanf("%s",str[i]);}for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j)continue;map[i][j]=maxpre(i,j);}}printf("%d\n",KM());}return 0;}