티스토리 뷰

알고리즘 관련/BOJ

BOJ)9413 제주도 관광

JASON 자손9319 2017. 3. 13. 18:12

문제: icpc.me/9413


시작 지점과 도착 지점 그리고 중간 경로상의 모든 정점들이 겹치지 않게 두 경로를 만들 때 가장 많은 정점을 순회하는 경우의 순회한 정점 수를 출력하는 문제이다.


우리는 정점을 분할 시킨 뒤 정점 사이의 capacity를 1로 주어서 정점이 중복 선택 안되게 가능하고 가장 많은 정점은 maximum 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
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#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;
    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);
    }
    vector<int> pv, pe;
    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) {
        queue<int> qu;
        vector<int> v(n + 10);
        vector<int> dist(n + 1, INF);
        qu.push(src);
        v[src] = 1;
        dist[src] = 0;
        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) {
                    pv[there] = here;
                    pe[there] = i;
                    dist[there] = dist[here] + vt[here][i].cost;
                    if (!v[there]) {
                        v[there] = 1;
                        qu.push(there);
                    }
                }
            }
        }
        return dist[sink] != INF;
    }
    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 += minFlow*vt[prev][idx].cost;
            }
        }
        return cost;
    }
};
int t, n, m;
int main() {
    scanf("%d"&t);
    while (t--) {
        scanf("%d%d"&n, &m);
        MCMF mcmf(* n + 5);
        mcmf.addEdge(* n + 3* n + 102);
        mcmf.addEdge(* n + 2* n + 402);
        for (int i = 1; i <= n; i++) {
            mcmf.addEdge(i, i + n, -11);
            mcmf.addEdge(* n + 1, i, 01);
            mcmf.addEdge(n + i, * n + 201);
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            scanf("%d%d"&x, &y);
            mcmf.addEdge(x + n, y, 0, INF);
        }
        printf("%d\n"-mcmf.solve(* n + 3* n + 4));
    }
    return 0;
}
cs


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

BOJ)10937 두부 모판 자르기  (1) 2017.03.16
BOJ)11410 칙칙폭폭  (0) 2017.03.15
BOJ)9413 제주도 관광  (0) 2017.03.13
BOJ)2311 왕복 여행  (0) 2017.03.13
BOJ)8892 팰린드롬  (0) 2017.03.13
BOJ)13576 Prefix와 Suffix  (0) 2017.03.13
TAG
댓글
댓글쓰기 폼