#include <algorithm>
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define DEBUG
#ifdef DEBUG
#define DEBUG_CMD(cmd)                                                                             \
    do {                                                                                           \
        cmd;                                                                                       \
    } while (false)
#else
#define DEBUG_CMD(cmd)                                                                             \
    do {                                                                                           \
        ;                                                                                          \
    } while (false)
#endif
#define _DEBUG_CMD(cmd)                                                                            \
    do {                                                                                           \
        ;                                                                                          \
    } while (false)

const int MAXN = 4000 + 10;
const int INF = 0x3F3F3F3F;
int K, C, M;
int g[MAXN][MAXN];

void floyd()
{
    const int limit = K + C;
    for (int k = 0; k < limit; ++k) {
        for (int i = 0; i < limit; ++i) {
            for (int j = 0; j < limit; ++j) {
                if (g[i][j] != INF)
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}

int visited[MAXN];
int match[MAXN][1 << 4], cap[MAXN];

int dfs(int u, int max_distance, int max_cap)
{
    // for (int v = K; v < K + C; ++v) {
    for (int v = 0; v < K; ++v) {
        if (visited[v] == 0 && g[u][v] <= max_distance) {
            visited[v] = 1;
            if (cap[v] < max_cap) {
                match[v][cap[v]++] = u;
                return 1;
            }
            for (int i = 0; i < cap[v]; ++i) {
                if (dfs(match[v][i], max_distance, max_cap)) {
                    match[v][i] = u;
                    return 1;
                }
            }
        }
    }
    return 0;
}

int hungarian(int max_distance, int max_cap)
{
    memset(cap, 0, sizeof(cap));
    memset(match, -1, sizeof(match));
    // for (int i = 0; i < K; ++i) {
    for (int i = K; i < K + C; ++i) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i, max_distance, max_cap) != 1) {
            return 0;
        }
    }
    return 1;
}

int main(int argc, char **argv)
{
    scanf("%d%d%d", &K, &C, &M);
    int limit = K + C;
    int lo = INF, hi = 0;
    for (int i = 0; i < limit; ++i) {
        for (int j = 0; j < limit; ++j) {
            scanf("%d", &g[i][j]);
            hi = max(g[i][j], hi);
            if (g[i][j] == 0) {
                g[i][j] = INF;
            }
            lo = min(g[i][j], lo);
        }
    }
    floyd();
    _DEBUG_CMD({
        for (int i = 0; i < K + C; ++i) {
            for (int j = 0; j < K + C; ++j) {
                printf("%d ", g[i][j]);
            }
            printf("\n");
        }
    });
    int res = 0;
    hi = 1000000; // hi may change subject to floyd.
    lo = 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (hungarian(mid, M)) {
            res = mid;
            hi = mid;
        }
        else {
            lo = mid + 1;
        }
    }
    // assert(lo == res);
    // assert(hi == res);
    printf("%d\n", res);
    return 0;
};

• Re:对表找不到问题, 但是WA, 代码在这里, 谁能给个test case? (91) NetWilliam 2021-02-25 08:35:38