题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3718
题意：有一堆答题情况和正确答案，问每一个答题情况的正确率最大是多少。
给每一对答案和答题情况的字母做映射，每次映射权值+1，这样会构造出一个二分图。在这个二分图上做最大匹配结果除以题目数量就是正确率。
1 #include2 using namespace std; 3 4 const int maxm = 10100; 5 const int maxn = 80; 6 const int inf = 0x3f3f3f3f; 7 int n, m, k; 8 int nx,ny; 9 int G[maxn][maxn];10 int linker[maxn],lx[maxn],ly[maxn];11 int slack[maxn];12 bool visx[maxn],visy[maxn];13 char ans[maxm];14 char stu[maxm];15 16 bool dfs(int x) {17 visx[x] = true;18 for(int y = 0; y < ny; y++) {19 if(visy[y])continue;20 int tmp = lx[x] + ly[y] - G[x][y];21 if(tmp == 0) {22 visy[y] = true;23 if(linker[y] == -1 || dfs(linker[y])) {24 linker[y] = x;25 return true;26 }27 }28 else if(slack[y] > tmp)29 slack[y] = tmp;30 }31 return false;32 }33 int km() {34 memset(linker,-1,sizeof(linker));35 memset(ly,0,sizeof(ly));36 for(int i = 0;i < nx;i++) {37 lx[i] = -inf;38 for(int j = 0;j < ny;j++)39 if(G[i][j] > lx[i])40 lx[i] = G[i][j];41 }42 for(int x = 0;x < nx;x++) {43 for(int i = 0;i < ny;i++)44 slack[i] = inf;45 while(true) {46 memset(visx,false,sizeof(visx));47 memset(visy,false,sizeof(visy));48 if(dfs(x))break;49 int d = inf;50 for(int i = 0;i < ny;i++)51 if(!visy[i] && d > slack[i])52 d = slack[i];53 for(int i = 0;i < nx;i++)54 if(visx[i])55 lx[i] -= d;56 for(int i = 0;i < ny;i++) {57 if(visy[i])ly[i] += d;58 else slack[i] -= d;59 }60 }61 }62 int res = 0;63 for(int i = 0;i < ny;i++)64 if(linker[i] != -1)65 res += G[linker[i]][i];66 return res;67 }68 69 int main() {70 // freopen("in", "r", stdin);71 int T;72 scanf("%d", &T);73 nx = ny = 26;74 while(T--) {75 scanf("%d%d%d",&n,&k,&m);76 for(int i = 0; i < n; i++) {77 cin >> ans[i];78 }79 for(int _ = 0; _ < m; _++) {80 for(int i = 0; i < n; i++) {81 cin >> stu[i];82 }83 memset(G, 0, sizeof(G));84 for(int i = 0; i < n; i++) {85 G[stu[i]-'A'][ans[i]-'A']++;86 }87 printf("%.4lf\n", (double)km()/(double)n);88 }89 }90 91 return 0;92 }