題意：給定兩個關系矩陣，分別表示雇主和雇員的相互好感度，好感度為1最優，N最差。如果一個人與好感度為P的人匹配的話，差值為P-1，現在要求是的總共的差值最小的匹配方法，并且輸出所有的匹配方案。

解法：將兩兩關系矩陣轉化為邊上的權值，然后進行一次最大匹配，最后dfs枚舉輸出結果，數據中給的矩陣上下顛倒了。

代碼如下：

#include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> 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; }

?

轉載于:https://www.cnblogs.com/Lyush/archive/2013/04/10/3013366.html

總結

以上是生活随笔為你收集整理的POJ-2400 Supervisor, Supervisee 带权值匹配+枚举所有匹配情况的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。