티스토리 뷰

알고리즘 관련/BOJ

BOJ)8992 집기 게임

JASON 자손9319 2017. 3. 20. 23:25

문제: icpc.me/8992


두 선분을 최대한 집으면서 점수를 최대한 많이 얻으려고 할 때 집을 수 있는 선분의 개수와 최대 점수를 구하는 문제이다.


우리는 두선분을 집는걸 우선시 해야하므로 두선분을 동시에 집는걸 capacity를 이용하여 모델링해주며 이 때 두선분을 집을 때 얻는 점수를 cost로 모델링해준 뒤 MCMF를 통하여 답을 구해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define INF 987654321
using namespace std;
struct MCMF {
    int n;
    struct Edge {
        int v, cost, cap, rev;
        Edge(int v, int cost, int cap, int rev)
            :v(v), cost(cost), cap(cap), rev(rev) {}
    };
    vector<vector<Edge>> vt;
    vector<int> pv, pe;
    void addEdge(int s, int e, int cost, int cap) {
        vt[s].emplace_back(e, cost, cap, vt[e].size());
        vt[e].emplace_back(s, -cost, 0, vt[s].size() - 1);
    }
    MCMF(int n) : n(n) {
        vt.resize(n + 1);
        pv.assign(n + 1-1);
        pe.assign(n + 1-1);
    }
    bool spfa(int src, int sink) {
        vector<int> v(n + 10);
        vector<int> dist(n + 1, INF);
        queue<int> qu;
        qu.push(src);
        dist[src] = 0;
        v[src] = 1;
        while (qu.size()) {
            int here = qu.front();
            qu.pop();
            v[here] = 0;
            for (int i = 0; i<vt[here].size(); i++) {
                int there = vt[here][i].v;
                int cap = vt[here][i].cap;
                if (cap&&dist[there]>dist[here] + vt[here][i].cost) {
                    dist[there] = dist[here] + vt[here][i].cost;
                    pv[there] = here;
                    pe[there] = i;
                    if (!v[there]) {
                        v[there] = 1;
                        qu.push(there);
                    }
                }
            }
        }
        return dist[sink] != INF;
    }
    pair<int,int> solve(int src, int sink) {
        int flow = 0, cost = 0;
        while (spfa(src,sink)) {
            int minFlow = INF;
            for (int crt = sink; crt != src; crt = pv[crt]) {
                int prev = pv[crt];
                int idx = pe[crt];
                minFlow = min(minFlow, vt[prev][idx].cap);
            }
            for (int crt = sink; crt != src; crt = pv[crt]) {
                int prev = pv[crt];
                int idx = pe[crt];
                vt[prev][idx].cap -= minFlow;
                vt[crt][vt[prev][idx].rev].cap += minFlow;
                cost += vt[prev][idx].cost*minFlow;
            }
            flow += minFlow;
        }
        return{ flow,cost };
    }
};
int t, n, m, x, y, z, w, q;
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d%d"&n, &m);
        vector<pair<pair<intint>, pair<intint>>> px(n + 1), py(m + 1);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d%d%d"&x, &y, &z, &w, &q);
            if (x > z)swap(x, z);
            px[i] = { {x,z},{y,q} };
        }
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d%d%d"&x, &y, &z, &w, &q);
            if (y > w)swap(y, w);
            py[i] = { {y,w},{x,q} };
        }
        MCMF mcmf(n + m + 2);
        for (int i = 1; i <= n; i++) {
            mcmf.addEdge(n + m + 1, i, 01);
            for (int j = 1; j <= m; j++) {
                if (px[i].first.first <= py[j].second.first&&py[j].second.first <= px[i].first.second&&py[j].first.first <= px[i].second.first&&px[i].second.first <= py[j].first.second) 
                    mcmf.addEdge(i, j + n, -px[i].second.second*py[j].second.second, 1);
            }
        }
        for (int j = 1; j <= m; j++)
            mcmf.addEdge(j + n, n + m + 201);
        pair<intint> r = mcmf.solve(n + m + 1, n + m + 2);
        printf("%d %d\n", r.first, -r.second);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)7535 A Bug's Life  (0) 2017.03.22
BOJ)3747 완벽한 선거!  (0) 2017.03.22
BOJ)8992 집기 게임  (0) 2017.03.20
BOJ)10937 두부 모판 자르기  (1) 2017.03.16
BOJ)11410 칙칙폭폭  (0) 2017.03.15
BOJ)9413 제주도 관광  (0) 2017.03.13
TAG
댓글
댓글쓰기 폼