티스토리 뷰

알고리즘 관련/BOJ

BOJ)2311 왕복 여행

JASON 자손9319 2017. 3. 13. 13:59

문제:icpc.me/2311


N개의 나라들이 있을 때 1~N까지 도시를 왕복할 때의 최소비용을 구하는 문제이다. 단 이 때 한번 갔던 경로로는 다시 이동할 수 없다.


우리는 소스->1->N->싱크로 그래프를 모델링 해준 뒤 소스->1 N->싱크의 간선만 capacity를 2로 주고 나머지 간선의 capacity를 1로 준 뒤 MCMF를 이용하여 mincost를 구할 수 있다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
int n, m;
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);
}
bool spfa() {
    vector<int> v(n + 30);
    vector<int> dist(n + 3, INF);
    queue<int> qu;
    qu.push(n + 1);
    dist[n + 1= 0;
    v[n + 1= 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[n + 2!= INF;
}
int solve() {
    int cost = 0, flow = 0;
    while (spfa()) {
        int minFlow = INF;
        for (int crt = n + 2; crt != n + 1; crt = pv[crt]) {
            int prev = pv[crt];
            int idx = pe[crt];
            minFlow = min(minFlow, vt[prev][idx].cap);
        }
        for (int crt = n + 2; crt != n + 1; 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;
        }
    }
    return cost;
}
int main() {
    scanf("%d%d"&n, &m);
    vt.resize(n + 3);
    pv.assign(n + 3-1);
    pe.assign(n + 3-1);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d%d%d"&x, &y, &z);
        addEdge(x, y, z, 1);
        addEdge(y, x, z, 1);
    }
    addEdge(n + 1102);
    addEdge(n, n + 202);
    printf("%d\n", solve());
    return 0;
}
cs


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

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
BOJ)13506 카멜레온 부분 문자열  (0) 2017.03.12
TAG
댓글
댓글쓰기 폼