POJ 2400 Supervisor, Supervisee（KM二分图最大权值匹配）题解

题意：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 =  + ;

const int MOD = 1e9 + ;

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 = ; y < ny; y++){

        if(visy[y]) continue;

        int tmp = lx[x] + ly[y] - g[x][y];

        if(tmp == ){

            visy[y] = true;

            if(linker[y] == - || dfs(linker[y])){

                linker[y] = x;

                return true;

            }

        }

        else if(slack[y] > tmp){

            slack[y] = tmp;

        }

    }

    return false;

}

int km(){

    memset(linker, -, sizeof(linker));

    memset(ly, , sizeof(ly));

    for(int i = ; i < nx; i++){

        lx[i] = -INF;

        for(int j = ; j < ny; j++){

            if(g[i][j] > lx[i]){

                lx[i] = g[i][j];

            }

        }

    }

    for(int x = ; x < nx; x++){

        for(int i = ; 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 = ; i < ny; i++)

                if(!visy[i] && d > slack[i])

                    d = slack[i];

            for(int i = ; i < nx; i++)

                if(visx[i])

                    lx[i] -= d;

            for(int i = ; i < ny; i++){

                if(visy[i]) ly[i] += d;

                else slack[i] -= d;

            }

        }

    }

    int res = ;

    for(int i = ; i < ny; i++){

        if(linker[i] != -)

            res += g[linker[i]][i];

    }

    return res;

}

int ans[maxn], vis[maxn];

int n, t, ret, num, ca = ;

void DFS(int u, int sco){

    if(sco < ret) return;

    if(u == n){

        if(sco == ret){

            printf("Best Pairing %d\n", num++);

            for(int i = ; i < n; i++){

                printf("Supervisor %d with Employee %d\n", i + , ans[i]);

            }

        }

        return;

    }

    for(int i = ; i < n; i++){

        if(vis[i]) continue;

        vis[i] = ;

        ans[u] = i + ;

        DFS(u + , sco + g[u][i]);

        vis[i] = ;

    }

}

int main(){

    scanf("%d", &t);

    while(t--){

        num = ;

        scanf("%d", &n);

        memset(g, , sizeof(g));

        for(int i = ; i < n; i++){ //雇员i对老板s

            for(int j = ; j < n; j++){

                int s;

                scanf("%d", &s);

                s--;

                g[s][i] += -j;

            }

        }

        for(int i = ; i < n; i++){ //老板i对雇员s

            for(int j = ; 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 != ) printf("\n");

        printf("Data Set %d, Best average difference: %lf\n", ca++, f);

        memset(vis, , sizeof(vis));

        num = ;

        DFS(, );

    }

    return ;

}