Codeforces Beta Round 17 - Hierarchy 링크
(2023.05.01 기준 Difficulty *1500)

문제

상사-부하 관계로 이루어진 트리 구조로 회사 사원들을 배치하려고 한다.
n명의 사원의 자격 수치가 주어진다.
그리고 사원 a가 돈 c를 받고 사원 b의 상사가 될 준비가 되어 있다는 요청이 m개가 있다. 모든 요청에서의 사원 a가 사원 b보다 자격 수치가 높다. 이 때, 트리 구조로 회사 사원들을 배치할 때의 최소한의 비용 출력

알고리즘

자격 수치가 정해져 있으므로 싸이클이 없는 요청들(간선들)이다. 그러면 DAG이므로 위상 정렬

풀이

위상 정렬을 하자. 근데 위상 정렬을 준비하는 과정에서 진입 차수가 0인 정점이 2개 이상이라면 -1을 출력해야 한다. 진입을 받는다는 것은 곧, 상사가 되어줄 수 있는 후보자들이 있다는 것인데, 만약 진입 차수가 0이면 자기의 상사가 되어줄 사람이 없다는 것이다. 이러한 사람이 2명 이상이라면 문제 조건을 충족하지 못한다.

코드

• C++

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

typedef pair<int, int> pii;
const int inf = 1e7;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, qj[1001];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> qj[i];

    int m, a, b, c, ind[n]; fill(ind, ind + n, 0);
    vector<pii> graph[n]; // supervisor -> surbodinate graph
    cin >> m;
    for (int i = 0; i < m; i++){
        cin >> a >> b >> c;
        graph[--a].push_back({--b, c});
        ind[b]++;
    }

    vector<int> q;
    for (int i = 0; i < n; i++) if (!ind[i]) q.push_back(i);

    // The vertex with indegree 0 is the starting vertex of DAG.
    // If there are multiple starting vertices,
    // there will be at least two employees who are not assigned a supervisor. So output -1.
    if (q.size() > 1){
        cout << -1;
        return 0;
    }

    int result = 0, cost[n]; fill(cost, cost + n, inf);
    while (!q.empty()){
        a = q.back(), q.pop_back();
        for (pii bc: graph[a]){
            b = bc.f, c = bc.s;
            cost[b] = min(cost[b], c);
            if (!--ind[b]){ // If indegree of the vertex is 0, cost of the vertex is set.
                result += cost[b];
                q.push_back(b);
            }
        }
    }
    cout << result;
}

• Python

import sys; input = sys.stdin.readline
from math import inf

n = int(input())
qj = list(map(int, input().split()))

graph = [[] for _ in range(n)] # supervisor -> surbodinate graph
ind = [0] * n
for _ in range(int(input())):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    graph[a].append((b, c))
    ind[b] += 1

queue = []
for i in range(n):
    if not ind[i]:
        queue.append(i)

# The vertex with indegree 0 is the starting vertex of DAG.
# If there are multiple starting vertices,
# there will be at least two employees who are not assigned a supervisor. So output -1.
if len(queue) > 1:
    print(-1)
    exit()

result = 0
cost = [inf] * n
while queue:
    a = queue.pop()
    for b, c in graph[a]:
        cost[b] = min(cost[b], c)
        ind[b] -= 1
        if not ind[b]: # If indegree of the vertex is 0, cost of the vertex is set.
            result += cost[b]
            queue.append(b)
print(result)