티스토리 뷰

알고리즘 관련/BOJ

BOJ)11410 칙칙폭폭

JASON 자손9319 2017. 3. 15. 23:51

문제: icpc.me/11410


기차가 1->N까지 이동할 때 도시 i에서 j로 이동하는 사람의 수와 그때 기차요금이 주어질 때 기차에 동시에 최대 p명의 사람이 탈 수 있을 때 기차가 낼 수 있는 최대 수익을 출력하는 문제이다.


i->i+1(i = 1~N)에 대하여 capcity를 INF, cost를 0으로 간선을 생성해주고  i 에서 j로 이동하는 경우에 이동하는 사람의 수를 capacity로 기차요금을 cost로 간선을 생성해 준 뒤 소스에서 ->1로  N에서 -> 싱크로 capacity p의 간선을 연결해 준 뒤 MCMF를 통하여 maximum cost를 구해주면 된다.


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
#include <cstdio>
#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;
    MCMF(int n) :n(n) {
        vt.resize(n + 1);
        pv.assign(n + 1-1);
        pe.assign(n + 1-1);
    }
    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(int src, int sink) {
        queue<int> qu;
        vector<int> v(n + 10);
        vector<int> dist(n + 1, INF);
        dist[src] = 0;
        qu.push(src);
        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;
    }
    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 -cost;
    }
};
int n, p, x, a[51][51];
int main() {
    scanf("%d%d"&n, &p);
    MCMF mcmf(n + 3);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            scanf("%d"&a[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            scanf("%d"&x);
            mcmf.addEdge(i, j, -x, a[i][j]);
        }
    }
    for (int i = 1; i < n; i++)
        mcmf.addEdge(i, i + 10, INF);
    mcmf.addEdge(n + 110, p);
    mcmf.addEdge(n, n + 20, p);
    printf("%d\n", mcmf.solve(n + 1, n + 2));
    return 0;
}
cs


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

BOJ)8992 집기 게임  (0) 2017.03.20
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
TAG
댓글
댓글쓰기 폼