hdu 3722 Card Game 二分图的最大权匹配
题目可以转化为2个集合，x集合和y集合，其中的元素是1-n个字符串。
首先预处理点与点的边权，然后直接用二分图的最大权匹配模板。
#include<stdio.h>#include<string.h>#define N 210#define inf 0x3fffffffint map[N][N],match[N],lx[N],ly[N],sx[N],sy[N],d[N],n;int find(int x){ sx[x]=1; for(int i=0;i<n;i++) { if(sy[i]==1)continue; int temp=lx[x]+ly[i]-map[x][i]; if(temp==0) { sy[i]=1; if(match[i]==-1||find(match[i])==1) { match[i]=x; return 1; } } else d[i]=d[i]>temp?temp:d[i]; } return 0;}int KM(){ int i,j,k,sum,min; memset(match,-1,sizeof(match)); memset(ly,0,sizeof(ly)); for(i=0;i<n;i++) { lx[i]=map[i][0]; for(j=1;j<n;j++) if(map[i][j]>lx[i]) lx[i]=map[i][j]; } for(i=0;i<n;i++) { for(j=0;j<n;j++) d[j]=inf; while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); if(find(i)==1)break; min=inf; for(k=0;k<n;k++) if(sy[k]==0&&min>d[k]) min=d[k]; for(j=0;j<n;j++) { if(sx[j]==1)lx[j]-=min; if(sy[j]==1)ly[j]+=min; } } } sum=0; for(i=0;i<n;i++) sum+=map[match[i]][i]; return sum;}int main(){ int i,j,k,sum,p; char str[201][1001]; while(scanf("%d",&n)!=-1) { for(i=0;i<n;i++) scanf("%s",str[i]); memset(map,0,sizeof(map)); for(i=0;i<n;i++) for(j=0;j<n;j++) { for(p=strlen(str[i])-1,k=0;str[j][k]&&p>=0;p--,k++) { if(str[i][p]!=str[j][k])break; } map[i][j]=k; } sum=KM(); printf("%d\n",sum); } return 0;}