题意：给定两个关系矩阵，分别表示雇主和雇员的相互好感度，好感度为1最优，N最差。如果一个人与好感度为P的人匹配的话，差值为P-1，现在要求是的总共的差值最小的匹配方法，并且输出所有的匹配方案。
解法：将两两关系矩阵转化为边上的权值，然后进行一次最大匹配，最后dfs枚举输出结果，数据中给的矩阵上下颠倒了。
代码如下：
#include#include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;int N, sum, cnt;int mp1[20][20], mp2[20][20];int w[20][20];int lx[20], ly[20], sx[20], sy[20];int match[20], slack[20];void build() { for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { w[i][j] = -mp1[i][j]-mp2[i][j]; // 转化为最大匹配问题 } }}bool path(int u) { sx[u] = 1; for (int i = 1; i <= N; ++i) { if (sy[i]) continue; int t = lx[u]+ly[i]-w[u][i]; if (!t) { sy[i] = 1; if (!match[i] || path(match[i])) { match[i] = u; return true; } } else { slack[i] = min(slack[i], t); } } return false;}void KM() { memset(match, 0, sizeof (match)); memset(ly, 0, sizeof (ly)); memset(lx, 0x80, sizeof (lx)); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { lx[i] = max(lx[i], w[i][j]); } } for (int i = 1; i <= N; ++i) { memset(slack, 0x3f, sizeof (slack)); while (1) { memset(sx, 0, sizeof (sx)); memset(sy, 0, sizeof (sy)); if (path(i)) break; int d = INF; for (int j = 1; j <= N; ++j) { if (!sy[j]) d = min(d, slack[j]); } for (int j = 1; j <= N; ++j) { if (sx[j]) lx[j] -= d; if (sy[j]) ly[j] += d; else slack[j] -= d; } } }}void dfs(int u, int tot, int deep) { if (tot < sum) return; if (deep == N) { // 匹配数量达到N printf("Best Pairing %d\n", ++cnt); for (int i = 1; i <= N; ++i) { printf("Supervisor %d with Employee %d\n", i, match[i]); } return; } for (int i = 1; i <= N; ++i) { if (!sy[i]) { sy[i] = 1; match[u] = i; dfs(u+1, tot+w[u][i], deep+1); sy[i] = 0; } }}void output(int ca) { double ret = 0; sum = cnt = 0; for (int i = 1; i <= N; ++i) { ret += w[match[i]][i]; sum += w[match[i]][i]; } ret = fabs(-ret / (2*N)); printf("Data Set %d, Best average difference: %f\n", ca, ret); memset(sy, 0, sizeof (sy)); dfs(1, 0, 0);}int main() { int T, x, ca = 0; scanf("%d", &T); while (T--) { scanf("%d", &N); for (int i = 1; i <= N; ++i) { for (int j = 0; j < N; ++j) { scanf("%d", &x); mp1[x][i] = j; // 对第x个候选人的好感度排第j } } for (int i = 1; i <= N; ++i) { for (int j = 0; j < N; ++j) { scanf("%d", &x); mp2[i][x] = j; } } build(); KM(); output(++ca); if (T) puts(""); } return 0; }