출발지에서 병원까지 <=s를 만족하며 최대 몇명을 보낼 수 있는가를 물어보는 문제다.


"매 단위시간마다 p명이 도로에 들어설 수 있으며 지나가는데는 단위시간 t가 걸린다"는 도로의 설명이 조금 헷갈릴 수 있는데


단위시간마다 정원p명의 엘리베이터를 운행한다 는 개념으로 이해했다.


그러므로 간선 a를 연결할 때 시작시간이 0~s인 a를 모두 저장했다. source->시작지점, 병원->sink로도 0~s로 모두 저장했으며


bfs를 돌릴 때 시작시간을 0~s까지 순차적으로 검색하게 했다.



<코드>

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
122
123
124
125
126
#include <stdio.h>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef pair<int, int> pii;
 
struct MF {
    struct E {
        // to, 사람수, 도로 진입시각, 통과시간
        int t, c, st, tc;
        E *rev;
        E(int t, int c, int st, int tc) : t(t), c(c), st(st), tc(tc) {}
    };
    int n, s, k, limit;
    vector<vector<E *>> g;
    vector<int> c;
    vector<pii> f;
    MF(int n, int s, int k) : n(n), s(s), k(k) {
        g.resize(n);
        c.resize(n);
        f.resize(n);
    }
    void init(int x, int y) {
        n = x;
        limit = y;
        for (int i = 0; i < n; i++) 
            g[i].clear();
        g[k].clear();
    }
    void aE(int u, int v, int w, int st, int tc) {
        E *ori = new E(v, w, st, tc);
        E *rev = new E(u, 0, st, tc);
        ori->rev = rev;
        rev->rev = ori;
        g[u].push_back(ori);
        g[v].push_back(rev);
    }
    int bfs(int tl) {
        for (int i = 0; i < n; i++) {
            c[i] = -1;
            f[i] = { -1,-1 };
        }
        c[k] = -1;
        f[k] = { -1,-1 };
        queue<int> q;
        q.push(s);
        c[s] = tl;
        while (q.size()) {
            int x = q.front();
            q.pop();
            if (c[k] >= 0) break;
            for (int i = 0; i < g[x].size(); i++) {
                if (c[x] + g[x][i]->tc <= limit && c[x] == g[x][i]->st && c[g[x][i]->t] == -1 && g[x][i]->c > 0) {
                    q.push(g[x][i]->t);
                    c[g[x][i]->t] = c[x] + g[x][i]->tc;
                    f[g[x][i]->t] = { x,i };
                }
            }
        }
        if (c[k] == -1) return 0;
        int x = k;
        int co = g[f[x].first][f[x].second]->c;
        while (f[x].first != -1) {
            co = min(co, g[f[x].first][f[x].second]->c);
            x = f[x].first;
        }
        x = k;
        while (f[x].first != -1) {
            if (f[x].first == 0) {
                for (auto i : g[0]) {
                    i->c -= co;
                    i->rev->c += co;
                }
            }
            else {
                E *e = g[f[x].first][f[x].second];
                e->c -= co;
                e->rev->c += co;
            }
            x = f[x].first;
        }
        return co;
    }
    int flow() {
        int ans = 0;
        for (int i = 0; i < limit; i++) {
            while (1) {
                int res = bfs(i);
                if (!res) break;
                ans += res;
            }
        }
        return ans;
    }
};
 
 
int main() {
    int tc;
    scanf("%d", &tc);
    MF mf = MF(1002, 0, 1001);
    while (tc--) {
        int n, i, g, s, m;
        scanf("%d%d%d%d%d", &n, &i, &g, &s, &m);
        mf.init(n + 2, s);
        for (int j = 0; j <= s; j++)
            mf.aE(mf.s, i, g, j, 0);
        while (m--) {
            scanf("%d", &n);
            for (int j = 0; j <= s; j++)
                mf.aE(n, mf.k, 101, j, 0);
        }
        scanf("%d", &m);
        int a, b, p, t;
        while (m--) {
            scanf("%d%d%d%d", &a, &b, &p, &t);
            for (int j = 0; j <= s; j++)
                mf.aE(a, b, p, j, t);
        }
        printf("%d\n", mf.flow());
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'BOJ' 카테고리의 다른 글

1717 집합의 표현  (0) 2017.09.06
1649 택시  (1) 2017.09.06
1574 룩 어택  (0) 2017.09.04
10026 적록색약  (0) 2017.09.01
6603 로또  (0) 2017.09.01

+ Recent posts

티스토리툴바