Strahler 순서




위상정렬의 변형문제.

strachler 순서가 정해지는 데 일련의 규칙이 있고, 따라서 간선을 지울 때 다른 작업을 추가로 해줘야 한다.


먼저 진입차수가 0인 노드들의 strachler 순서는 0이다. 이제 이 노드들이 큐에서 꺼내질 때, 노드의 진출 간선들을 지우면서

규칙에 따른 작업을 한다.


규칙은 다음과 같다.

  • 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다.


그래서 각 노드는 순서값, 들어오는 강의 순서들, 가장 큰 값을 기억해야 한다.


이후에는 규칙대로 풀면 된다.


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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct Strahler {
    int max, order_cnt[1001], order;
};
 
int in[1001];
int k, kk, m, p, a, b;
 
int main() {
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d %d", &kk, &m, &p);
        for (int i = 1; i <= m; ++i)
            in[i] = 0;
 
        vector<vector<int>> vec(m + 1);
        for (int i = 0; i < p; ++i) {
            scanf("%d %d", &a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
        vector<Strahler> st(m + 1);
        queue<int> q;
        for (int i = 1; i <= m; ++i) {
            if (!in[i]) {
                q.push(i);
                st[i].order = 1;
            }
        }
 
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
 
            for (auto next : vec[cur]) {
                if (st[next].max < st[cur].order)
                    st[next].max = st[cur].order;
 
                st[next].order_cnt[st[cur].order]++;
 
                in[next]--;
                if (!in[next]) {
                    if (st[next].order_cnt[st[next].max] == 1)
                        st[next].order = st[next].max;
                    else if (st[next].order_cnt[st[next].max] > 1)
                        st[next].order = st[next].max + 1;
                    q.push(next);
                }
            }
        }
        printf("%d %d\n", kk, st[m].order);
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 3665 최종 순위  (0) 2018.02.21
백준) 2637 장난감조립  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

ACM Craft


https://www.acmicpc.net/problem/1005



전의 게임 개발 (https://www.acmicpc.net/problem/1516)과 같은 문제다.


게임 개발은 모든 건물의 최소 건설 완료 시간을 물어봤다면, 이 문제는 한 건물만 물어본다.



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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int time[1001], in[1001];
int t, n, k, a, b, w;
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &time[i]);
            in[i] = 0;
        }
 
        vector<vector<int>> vec(n + 1);
        for (int i = 0; i < k; ++i) {
            scanf("%d %d", &a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
 
        vector<int> ans(n + 1);
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (!in[i]) {
                q.push(i);
                ans[i] = time[i];
            }
        }
 
        scanf("%d", &w);
        while (!q.empty()) {
            int m = 0;
            int cur = q.front();
            q.pop();
            if (cur == w)
                break;
 
            for (auto next : vec[cur]) {
                in[next]--;
 
                if (ans[next] < ans[cur] + time[next])
                    ans[next] = ans[cur] + time[next];
 
                if (!in[next])
                    q.push(next);
            }
        }
        printf("%d\n", ans[w]);
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 2637 장난감조립  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20

게임 개발


https://www.acmicpc.net/problem/1516



테크트리를 타고 모든 건물을 지어야 한다. 모든 건물을 짓는데 시간이 얼마나 들까?


생각해야 할 점은 건물들이 동시에 지어질 수 있다는 점이다.


예를 들어 현재 배럭과 벙커를 지을 수 있다면, 배럭을 짓는데 시간이 더 오래 걸리므로 배럭 건설시간이 정답이 된다.



큐는 현재 지을 수 있는 건물(진입차수가 0이 된 노드)을 담고 있으므로,


큐를 건설시간이 작은 순으로 정렬되는 우선순위 큐로 바꾼다면, 맨 뒤에 있는 배럭이 정답에 반영될 것이다.



다르게 말하자면,


a->b (10)// c->b (20)라는 테크트리에 대해, 


b를 짓기 위해선 a와 c를 둘 다 지어야 하지만, b를 짓기 위한 준비 시간은 c만 포함된다.



따라서 b로 진입하는 두 간선 중 가벼운 a가 먼저 지어지면서 간선이 없어지지만, 무거운 c간선이 남아있으므로


정답에 반영되지 않는다.


다음으로 c간선이 없어지면서 b를 지을 수 있게되었다. 이제 가장 무거웠던 c간선의 20초가 정답에 들어간다.


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
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
struct build {
    int num, time;
};
bool operator <(const build& a, const build& b) {
    if (a.time != b.time)
        return a.time > b.time;
    return a.num > b.num;
}
build buildings[501];
 
int n, a, b, c;
int in[501];
 
int main() {
    scanf("%d", &n);
    vector<vector<int>> vec(n + 1);
 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a);
        buildings[i].time = a;
 
        while (1) {
            scanf("%d", &a);
            if (a == -1)
                break;
 
            vec[a].push_back(i);
            in[i]++;
        }
    }
 
    priority_queue<build> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i])
            q.push({i,buildings[i].time});
    }
 
    while (!q.empty()) {
        int cur = q.top().num;
        q.pop();
 
        for (auto next : vec[cur]) {
            in[next]--;
            if (!in[next]) {
                buildings[next].time += buildings[cur].time;
                q.push({next, buildings[next].time});
            }    
        }
    }
 
    for (int i = 1; i <= n; ++i)
        printf("%d\n", buildings[i].time);
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

+ Recent posts

티스토리툴바