취미로 코딩하기

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

이번에 볼 문제는 백준 8992번 문제인 집기 게임이다.
문제는 아래 링크를 확인하자.

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

가로선의 집합을 한 쪽, 세로선의 집합을 다른 쪽에 두고, source와 각 가로선을 capacity 1, 각 세로선과 sink를 capacity 1의 간선으로 잇고 서로 교차하는 가로선과 세로선의 쌍 사이에 capacity 1, cost (두 선의 무게의 곱)의 간선을 그어 플로우 그래프를 만든 뒤 MCMF를 이용하여 문제를 해결하자.

간선의 cost의 부호를 뒤집어 계산하면 Maximum Cost Maximum Flow를 계산해낼 수 있다.

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

#define NODE 802
#define INF 1000000007
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> point;

struct line {
    point A, B;
    ll w;
    line() {};
    line(point A, point B, ll w) {
        this->A = A, this->B = B, this->w = w;
    }
};

int CCW(point A, point B, point C) {
    ll ccw = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
    if (ccw > 0) return 1;
    else if (ccw < 0) return -1;
    else return 0;
}

int lineintersectioncheck(line X, line Y) {
    int ccw1 = CCW(X.A, X.B, Y.A);
    int ccw2 = CCW(X.A, X.B, Y.B);
    int ccw3 = CCW(Y.A, Y.B, X.A);
    int ccw4 = CCW(Y.A, Y.B, X.B);

    if (ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0) {
        point X1, X2, Y1, Y2;
        if (X.A < X.B) {
            X1 = X.A, X2 = X.B;
        }
        else {
            X1 = X.B, X2 = X.A;
        }
        if (Y.A < Y.B) {
            Y1 = Y.A, Y2 = Y.B;
        }
        else {
            Y1 = Y.B, Y2 = Y.A;
        }
        if (X2 < Y1 || Y2 < X1) return 0;
        else if (X2 == Y1 || Y2 == X1) return 3;
        else return 2;
    }
    else {
        if (ccw1 * ccw2 <= 0 && ccw3 * ccw4 <= 0) {
            return 1;
        }
        else return 0;
    }
}

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);
}

line lineA[200], lineB[200];

void solve() {
    memset(edge, 0, sizeof(edge));
    memset(cost, 0, sizeof(cost));
    for (auto& v : G) v.clear();

    source = 400, sink = 401;
    int N, M; cin >> N >> M;
    for (int n = 0; n < N; n++) {
        ll x, y, xx, yy, w; cin >> x >> y >> xx >> yy >> w;
        lineA[n] = line(make_pair(x, y), make_pair(xx, yy), w);
    }
    for (int m = 0; m < M; m++) {
        ll x, y, xx, yy, w; cin >> x >> y >> xx >> yy >> w;
        lineB[m] = line(make_pair(x, y), make_pair(xx, yy), w);
    }

    for (int n = 0; n < N; n++) {
        edge[source][n] = 1;
        G[source].emplace_back(n);
        G[n].emplace_back(source);
    }
    for (int m = 0; m < M; m++) {
        edge[m + 200][sink] = 1;
        G[m + 200].emplace_back(sink);
        G[sink].emplace_back(m + 200);
    }

    for (int n = 0; n < N; n++) {
        for (int m = 0; m < M; m++) {
            if (lineintersectioncheck(lineA[n], lineB[m])) {
                ll c = lineA[n].w * lineB[m].w;
                edge[n][m + 200] = 1;
                cost[n][m + 200] = -c;
                cost[m + 200][n] = c;
                G[n].emplace_back(m + 200);
                G[m + 200].emplace_back(n);
            }
        }
    }

    auto p = MCMF();
    cout << p.first << ' ' << -p.second << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    while (T--) {
        solve();
    }
}