POJ 2400 KM+建圖

POJ 2400

題意

• n

  個部門

  n

  個員工,每個部門雇傭一個員工,部門希望雇傭每個員工的希望值不同,員工希望被雇傭的部門的希望值也不同, 求使得所有人希望值之和最大,輸出最優比對結果,若有多種,輸出所有

思路(借鑒大佬)

• 題目資料與描述不一樣,先給出的每個員工的對部門的希望值,然後才是每個部門的首選項,
• 将左部分作為部門,右部分作為員工,邊權為各自希望值之和, 用

  KM

  求出最大的希望值之和
• 要求輸出的 最好平均差（通過樣例了解）就是 (每個部門和員工都是最好比對的權值和- 最大權值比對和)/總個數
• 得到最好平均差還要

  dfs

  搜二分圖,把搜到的比對和KM求出的ans比較, 相等則說明是一組最大權值比對

• 為什麼

  w[][]

  還是負值? 不是求最大希望和嗎? 因為希望最大的在最開始,那麼換成

  w[to][i] = n-j

  等價于換成負數(體會一下)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int inf = 1<<30;
const int maxn = 25;
int w[maxn][maxn],la[maxn],lb[maxn],match[maxn];
int n,m,delta,cnt,ans;
bool va[maxn],vb[maxn];

int dfs(int u) {
    va[u] = 1;
    for (int i=1; i<=n; ++i) {
        if (!vb[i]) {
            if (la[u]+lb[i]-w[u][i] == 0) {
                vb[i] = 1;
                if (match[i]==-1 || dfs(match[i])) {
                    match[i] = u;
                    return 1;
                }
            } else delta = min(delta,la[u]+lb[i]-w[u][i]);
        }
    }
    return 0;
}

int KM() {
    for (int i=0; i<maxn; ++i) la[i] = -inf;
    memset(lb,0,sizeof lb);
    memset(match,-1,sizeof match);
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j)
            la[i] = max(la[i],w[i][j]);
    for (int i=1; i<=n; ++i) {
        while (1) {
            memset(va,0,sizeof va);
            memset(vb,0,sizeof vb);
            delta = inf;
            if (dfs(i)) break;
            for (int j=1; j<=n; ++j) {
                if (va[j]) la[j] -= delta;
                if (vb[j]) lb[j] += delta;
            }
        }
    }
    ans = 0;
    for (int i=1; i<=n; ++i)
        if (match[i]) ans += w[match[i]][i];
    return -ans;
}

void dfs(int u,int sum) {
    if (sum < ans) return ;//剪枝,因為邊權都為負數,目前和都小于ans,再加上負數不可能達到ans的值(這組全排列不是KM的比對)
    if (u > n) {// 前n位搜出來了,判斷搜出來的邊權和是否=ans
        if (sum != ans) return ;
        printf("Best Pairing %d\n",cnt++);
        for (int i=1; i<=n; ++i)
            printf("Supervisor %d with Employee %d\n",i,match[i]);
    } else {
        for (int i=1; i<=n; ++i) {
            if (!va[i]) {
                va[i] = 1;
                match[u] = i;
                dfs(u+1,sum+w[u][i]);
                va[i] = 0;
            }
        }
    }

}

int main () {
    freopen("1.in","r",stdin);
    int times,case1=1; cin >> times;
    while (times--) {
        scanf("%d",&n);
        memset(w,0,sizeof w);
        int to;
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j) {
                scanf("%d",&to);
                w[to][i] -= (j-1);
            }
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j) {
                scanf("%d",&to);
                w[i][to] -= (j-1);
            }
        printf("Data Set %d, Best average difference: %.6lf\n",case1++,KM()/(2.0*n));
        memset(va,0,sizeof va);
        cnt = 1;
        dfs(1,0);
        printf("\n");
    }
    return 0;
}