티스토리 뷰

알고리즘 관련/BOJ

BOJ)1745 숨기

JASON 자손9319 2017. 3. 29. 16:59

문제: icpc.me/1745


F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다.


우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다.


이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다.


이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.


이때 우리는 최소 시간을 구해야 하므로 플로이드 워셜을 통하여 각 방마다의 최소 거리를 구해준 뒤 


파라메트릭 서치를 통하여 mid보다 작은 모든 정점들을 I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 으로 모델링 해줌으로 서 여부를 파악한다.


정점이 약 f*f+2*f 개 가량이므로 디닉으로 maximum flow를 구하지 않는다면 TLE를 받을 수 있다.


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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#define INF 987654321
typedef long long ll;
using namespace std;
struct Dinic {
    ll n;
    struct Edge {
        ll v, cap, rev;
        Edge(ll v, ll cap, ll rev) :v(v), cap(cap), rev(rev) {}
    };
    vector<vector<Edge>> vt;
    void addEdge(ll s, ll e, ll c) {
        vt[s].emplace_back(e, c, vt[e].size());
        vt[e].emplace_back(s, 0, vt[s].size() - 1);
    }
    vector<ll> level, work;
    Dinic(ll n) :n(n) {
        vt.resize(n + 1);
        level.assign(n + 1-1);
        work.assign(n + 10);
    }
    bool bfs(ll src, ll sink) {
        level.assign(n + 1-1);
        queue<ll> qu;
        level[src] = 0;
        qu.push(src);
        while (qu.size()) {
            ll here = qu.front();
            qu.pop();
            for (auto i : vt[here]) {
                if (i.cap > && level[i.v] == -1) {
                    level[i.v] = level[here] + 1;
                    qu.push(i.v);
                }
            }
        }
        return level[sink] != -1;
    }
    ll dfs(ll sink, ll here, ll crtcap) {
        if (sink == here)return crtcap;
        for (ll &= work[here]; i < vt[here].size(); i++) {
            ll cap = vt[here][i].cap;
            ll there = vt[here][i].v;
            if (level[here] + == level[there] && cap>0) {
                ll c = dfs(sink, there, min(crtcap, cap));
                if (c) {
                    vt[here][i].cap -= c;
                    vt[there][vt[here][i].rev].cap += c;
                    return c;
                }
            }
        }
        return 0;
    }
    ll solve(ll src, ll sink) {
        ll ret = 0;
        while (bfs(src, sink)) {
            work.assign(n + 10);
            while (1) {
                ll flow = dfs(sink, src, INF);
                if (!flow)break;
                ret += flow;
            }
        }
        return ret;
    }
};
ll f, p, a[202][202], x, y, z, b[202], c[202], n;
int main() {
    memset(a, 0x3fsizeof(a));
    scanf("%lld%lld"&f, &p);
    for (ll i = 1; i <= f; i++) {
        scanf("%lld%lld"&b[i], &c[i]);
        n += b[i];
    }
    for (ll i = 0; i < p; i++) {
        scanf("%lld%lld%lld"&x, &y, &z);
        a[x][y] = min(z, a[x][y]);
        a[y][x] = min(z, a[y][x]);
    }
    for (ll i = 1; i <= f; i++) {
        for (ll j = 1; j <= f; j++) {
            for (ll k = 1; k <= f; k++) {
                if (j == k)a[j][k] = 0;
                if (a[j][i] + a[i][k] < a[j][k])
                    a[j][k] = a[j][i] + a[i][k];
            }
        }
    }
    ll lo = 0, hi = 1000000000010;
    while (lo < hi) {
        Dinic d(f*+ * f + 3);
        ll mid = (lo + hi) >> 1;
        for (ll i = 1; i <= f; i++) {
            for (ll j = 1; j <= f; j++) {
                if (a[i][j] <= mid) {
                    d.addEdge(i, i*+ j, INF);
                    d.addEdge(i*+ j, f*+ f + j, INF);
                }
            }
        }
        for (ll i = 1; i <= f; i++) {
            d.addEdge(f*+ * f + 1, i, b[i]);
            d.addEdge(f*+ f + i, f*+ * f + 2, c[i]);
        }
        ll r = d.solve(f*+ * f + 1, f*+ * f + 2);
        if (r == n)
            hi = mid;
        else
            lo = mid + 1;
    }
    if (lo > 1000000000001)
        printf("-1");
    else
        printf("%lld\n", lo);
    return 0;
}
cs


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

BOJ)2146 다리만들기  (0) 2017.03.30
BOJ)5427 불  (0) 2017.03.30
BOJ)1745 숨기  (0) 2017.03.29
BOJ)5397 키로거  (0) 2017.03.28
BOJ)2075 N번째 큰 수  (0) 2017.03.27
BOJ)1326 폴짝폴짝  (0) 2017.03.26
댓글
댓글쓰기 폼