hdu3722Card Game(KM最大带权匹配)
题目请戳这里
题目大意：给n个字符串，再给一个n的排列：p1,p2....pn。然后将第i个字符串贴到第pi个字符串后面，然后形成一个环。pi的首字符和第i个字符串的末尾字符就相邻，如果这2个字符相等，各自再向内延伸一个位置，知道这个环首尾字符不等为止。延伸的位置为该环的得分（如果pi == i，得分为0），对于每个排列，有n个这样的环，求得分和最大为多少。
题目分析：最大带权匹配！！以为是个字符串的题目，就没仔细看。。。
建图直接跑模版。。。
详情请见代码：
#include <iostream>#include<cstdio>#include<cstring>using namespace std;const int N = 205;const int M = 1005;const int inf = 0x3f3f3f3f;char s[N][M];int n;int lx[N],ly[N],w[N][N];bool cx[N],cy[N];int match[N];int slack;int getw(int x,int y){ int i,j; i = strlen(s[x]) - 1; j = 0; int lenj = strlen(s[y]) - 1; int ret = 0; while(i >= 0 && j <= lenj && s[x][i] == s[y][j]) i --,j ++,ret ++; return ret;}void predeal(){ int i,j; for(i = 1;i <= n;i ++) { for(j = 1;j <= n;j ++) if(i == j) w[i][j] = 0; else w[i][j] = getw(i,j); }}bool path(int u){ cx[u] = true; for(int v = 1;v <= n;v ++) { if(cy[v] == false) { int t = lx[u] + ly[v] - w[u][v]; if(t) { if(slack > t) slack = t; } else { cy[v] = true; if(match[v] == -1 || path(match[v])) { match[v] = u; return true; } } } } return false;}void KM(){ int ans = 0; int i,j; for(i = 1;i <= n;i ++) { lx[i] = -inf; ly[i] = 0; for(j = 1;j <= n;j ++) if(lx[i] < w[i][j]) lx[i] = w[i][j]; } memset(match,-1,sizeof(match)); for(i = 1;i <= n;i ++) { while(1) { memset(cx,false,sizeof(cx)); memset(cy,false,sizeof(cy)); slack = inf; if(path(i)) break; for(j = 1;j <= n;j ++) { if(cx[j]) lx[j] -= slack; if(cy[j]) ly[j] += slack; } } } for(i = 1;i <= n;i ++) ans += w[match[i]][i]; printf("%d\n",ans);}int main(){ while(scanf("%d",&n) != EOF) { for(int i = 1;i <= n;i ++) scanf("%s",s[i]); predeal(); KM(); } return 0;}