취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15504번 문제인 프로그래밍 대결이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/15504 

두 참가자가 대결하면 실력이 더 낮은 참가자는 떨어지고 최종적으로 한 사람이 남을 때까지 대결을 이어가므로, 실력이 가장 좋은 참가자를 제외한 모든 참가자 i는 자신보다 실력이 좋은 참가자와 정확히 한 번 대결하고 자신보다 실력이 나쁜 참가자와 Li - 1번 이하로 대결하게 된다.

각 참가자마다 그 자신보다 실력이 더 좋은 참가자를 제약에 맞춰 선택해 경쟁하되 그 모든 경우중 대회의 재미를 최대화하는 것은 MCMF를 이용해 구해낼 수 있다. 그래프를 잘 모델링해 값을 구해내자.

실력이 가장 좋은 참가자의 경우 자신보다 실력이 나쁜 참가자와 Li번 대결할 수 있음에 유의하자.

글쓴이의 경우 아래 코드의 82, 89번 라인에서 xor연산보다 -연산의 우선순위가 더 높은 것을 간과해 디버깅이 오래 걸렸다. 비트연산을 사용할 경우 연산의 우선순위에 유의하여 구현하자.

아래는 제출한 소스코드이다.

#define NODE 602
#define INF 1000000007
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int source = 0, sink = 801;
int edge[NODE][NODE], cost[NODE][NODE];
vector<int> G[NODE];

int par[NODE];
int stepcost[NODE];
int inque[NODE];

pair<int, int> MCMF() { // {maxflow, mincost}
    int retflow = 0, retcost = 0;
    while (1) {
        memset(par, -1, sizeof(par));
        memset(inque, 0, sizeof(inque));
        fill(stepcost, stepcost + NODE, INF);
        stepcost[source] = 0;

        queue<int> que;
        que.push(source);
        inque[source] = 1;

        while (!que.empty()) {
            int cur = que.front(); que.pop();
            inque[cur] = 0;
            for (auto& nxt : G[cur]) {
                if (edge[cur][nxt] > 0 && stepcost[cur] + cost[cur][nxt] < stepcost[nxt]) {
                    stepcost[nxt] = stepcost[cur] + cost[cur][nxt];
                    par[nxt] = cur;
                    if (!inque[nxt]) {
                        que.push(nxt);
                        inque[nxt] = 1;
                    }
                }
            }
        }

        if (par[sink] == -1) break;

        int flow = INF;
        for (int i = sink; i != source; i = par[i]) flow = min(flow, edge[par[i]][i]);
        for (int i = sink; i != source; i = par[i]) {
            retcost += cost[par[i]][i] * flow;
            edge[par[i]][i] -= flow;
            edge[i][par[i]] += flow;
        }
        retflow += flow;
    }

    return make_pair(retflow, retcost);
}

int A[301];
int H[301];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    source = 0, sink = 601;
    int N; cin >> N;
    
    int AMax = -1, AMaxidx = -1;
    for (int n = 1; n <= N; n++) {
        int& x = A[n]; cin >> x;
        if (x > AMax) AMax = x, AMaxidx = n;
    }
    for (int n = 1; n <= N; n++) cin >> H[n];
    
    for (int n = 1; n <= N; n++) {
        edge[source][n] = 1;
        G[source].emplace_back(n);
        G[n].emplace_back(source);
        for (int m = n + 1; m <= N; m++) {
            if (A[n] < A[m]) {
                edge[n][m + 300] = 1;
                cost[n][m + 300] = -((A[n] ^ A[m]) - H[n] - H[m]);
                cost[m + 300][n] = -cost[n][m + 300];
                G[n].emplace_back(m + 300);
                G[m + 300].emplace_back(n);
            }
            else {
                edge[m][n + 300] = 1;
                cost[m][n + 300] = -((A[m] ^ A[n]) - H[m] - H[n]);
                cost[n + 300][m] = -cost[m][n + 300];
                G[m].emplace_back(n + 300);
                G[n + 300].emplace_back(m);
            }
        }
    }

    for (int n = 1; n <= N; n++) {
        int c; cin >> c;
        if (n == AMaxidx)  edge[n + 300][sink] = c;
        else edge[n + 300][sink] = c - 1;
        G[n + 300].emplace_back(sink);
        G[sink].emplace_back(n + 300);
    }

    cout << -MCMF().second;
}