ZOJ - 2362 Beloved Sons 최대 가중치 매 칭

제목: 왕 은 N 명의 아들 이 있 습 니 다. 지금 은 모든 아들 이 결혼 하면 어느 정도 기쁨 을 얻 을 수 있 습 니 다. 왕자 번 호 는 1 - N 이 고 N 명의 여자 가 있 습 니 다. 똑 같이 1 - N 입 니 다. 모든 왕자 가 마음 에 드 는 여자 가 있 습 니 다. 지금 물 어보 면 문제 에서 정 한 스타일 과 가장 큰 것 을 만 들 수 있 습 니 다.
분석: 사실 제목 의 그 뿌리 번 호 는 연막탄 이 므 로 기쁨 치 의 제곱 에 만 관심 을 가지 면 된다.그러면 왕자 와 여자 사이 에 변 을 구성 하고 변 권 은 기쁨 치 의 제곱 이다. 모든 왕자 에 게 한 여자 의 변 권 을 0 으로 가상 하 는 것 은 모든 왕자 가 여자 가 짝 을 이 룰 수 있 도록 알고리즘 을 정확하게 집행 할 수 있 도록 하 는 것 이다.

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 405;
const int inf = 0x3f3f3f3f;
int n, m;
int like[N];
int w[N][N<<1];
int match[N<<1];
int lx[N], ly[N<<1], slack[N<<1];
int vx[N], vy[N<<1];
int marry[N];

bool path(int u) {
    vx[u] = 1;
    for (int v = 1; v <= m; ++v) {
        if (vy[v] || w[u][v] == -1) continue;
        int t = lx[u]+ly[v]-w[u][v];
        if (!t) {
            vy[v] = 1;
            if (!match[v] || path(match[v])) {
                match[v] = u;
                return true;
            }
        } else {
            slack[v] = min(slack[v], t);
        }
    }
    return false;
}

void KM() {
    memset(lx, 0x80, sizeof (lx));
    memset(ly, 0, sizeof (ly));
    memset(match, 0, sizeof (match));
    memset(marry, 0, sizeof (marry));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (w[i][j] != -1) {
                lx[i] = max(lx[i], w[i][j]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        memset(slack, 0x3f, sizeof (slack));
        while (1) {
            memset(vx, 0, sizeof (vx));
            memset(vy, 0, sizeof (vy));
            if (path(i)) break;
            int d = inf;
            for (int j = 1; j <= m; ++j) {
                if (!vy[j]) d = min(d, slack[j]);
            }
            if (d == inf) break;
            for (int j = 1; j <= n; ++j) {
                if (vx[j]) lx[j] -= d;
            }
            for (int j = 1; j <= m; ++j) {
                if (vy[j]) ly[j] += d;
                else slack[j] -= d;
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (match[i] && i <= n) {
            marry[match[i]] = i;
        }
    }
    for (int i = 1; i <= n; ++i) {
        printf(i == 1 ? "%d" : " %d", marry[i]);
    }
    puts("");
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(w, 0xff, sizeof (w));
        scanf("%d", &n);
        m = n << 1;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &like[i]);
        }
        int x, y;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            for (int j = 0; j < x; ++j) {
                scanf("%d", &y);
                w[i][y] = like[i] * like[i];
            }
            w[i][n+i] = 0;
        }
        KM();
    }
    return 0;
}