题意：n个老板n个员工，先给你n*n的数据，i行j列代表第i个老板第j喜欢的员工是谁，再给你n*n的数据，i行j列代表第i个员工第j喜欢的老板是谁，如果匹配到第k喜欢的人就会产生一个分数k-1。现在让你给老板和员工配对，希望得到的分数的平均数最少，并给出哪个老板匹配哪个员工，多种情况按字典序输出。
思路：题目中的input提示是错的...
这题就是km最大权值匹配的裸题，分数最小那就把权值变负，然后跑出最少的总分。因为n比较小，可以dfs求出所有情况。
代码：
#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> typedef long long ll; using namespace std; const int maxn = 50 + 10; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; int nx, ny; int g[maxn][maxn]; int linker[maxn], lx[maxn], ly[maxn]; int slack[maxn]; bool visx[maxn], visy[maxn]; bool dfs(int x){ visx[x] = true; for(int y = 0; y < ny; y++){ if(visy[y]) continue; int tmp = lx[x] + ly[y] - g[x][y]; if(tmp == 0){ visy[y] = true; if(linker[y] == -1 || dfs(linker[y])){ linker[y] = x; return true; } } else if(slack[y] > tmp){ slack[y] = tmp; } } return false; } int km(){ memset(linker, -1, sizeof(linker)); memset(ly, 0, sizeof(ly)); for(int i = 0; i < nx; i++){ lx[i] = -INF; for(int j = 0; j < ny; j++){ if(g[i][j] > lx[i]){ lx[i] = g[i][j]; } } } for(int x = 0; x < nx; x++){ for(int i = 0; i < ny; i++) slack[i] = INF; while(true){ memset(visx, false, sizeof(visx)); memset(visy, false, sizeof(visy)); if(dfs(x)) break; int d = INF; for(int i = 0; i < ny; i++) if(!visy[i] && d > slack[i]) d = slack[i]; for(int i = 0; i < nx; i++) if(visx[i]) lx[i] -= d; for(int i = 0; i < ny; i++){ if(visy[i]) ly[i] += d; else slack[i] -= d; } } } int res = 0; for(int i = 0; i < ny; i++){ if(linker[i] != -1) res += g[linker[i]][i]; } return res; } int ans[maxn], vis[maxn]; int n, t, ret, num, ca = 1; void DFS(int u, int sco){ if(sco < ret) return; if(u == n){ if(sco == ret){ printf("Best Pairing %d ", num++); for(int i = 0; i < n; i++){ printf("Supervisor %d with Employee %d ", i + 1, ans[i]); } } return; } for(int i = 0; i < n; i++){ if(vis[i]) continue; vis[i] = 1; ans[u] = i + 1; DFS(u + 1, sco + g[u][i]); vis[i] = 0; } } int main(){ scanf("%d", &t); while(t--){ num = 0; scanf("%d", &n); memset(g, 0, sizeof(g)); for(int i = 0; i < n; i++){ //雇员i对老板s for(int j = 0; j < n; j++){ int s; scanf("%d", &s); s--; g[s][i] += -j; } } for(int i = 0; i < n; i++){ //老板i对雇员s for(int j = 0; j < n; j++){ int s; scanf("%d", &s); s--; g[i][s] += -j; } } nx = ny = n; ret = km(); double f = -ret / 2.0 / n; if(ca != 1) printf(" "); printf("Data Set %d, Best average difference: %lf ", ca++, f); memset(vis, 0, sizeof(vis)); num = 1; DFS(0, 0); } return 0; }