POJ2400 Supervisor, Supervisee 带权值匹配+枚举所有匹配情况

题意：给定两个关系矩阵，分别表示雇主和雇员的相互好感度，好感度为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;    
}