AC-M-Solution-D. Maximum Sum of Minimum

작성일

https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_d

  • 배운걸 써먹었다는 거에 의의가 있다. Cat and Mouse 게임 문제에서 한번 위상정렬 순서로 탐색해야 하는 문제를 겪었었는데, 이 문제도 마찬가지다.
  • 아직 정해인지는 모르겠지만, 여튼 위상정렬순으로 값을 작은 순으로 배정하면 된다.
  • 근데 다른 사람들 풀이를 보니 걍 DFS로 풀고 inorder 값 집어넣어도 무방한것 같다.
  • 결국 문제를 이해하는게 가장 중요했던 문제.
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
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 10000;
vector<vector<int>> vt;
queue<int> q;
int in[MAXN+2];
int ci[MAXN+2];
int ans[MAXN+2];
int sum = 0;
int N;
 
int main() {
  ios::sync_with_stdio(false);
  cin >> N;
  vt.resize(N+1);
  for(int i = 0; i < N-1; i++) {
    int a, b;
    cin >> a >> b;
    vt[a].push_back(b);
    vt[b].push_back(a);
    in[a]++;
    in[b]++;
  }
 
  for(int i = 1; i <= N; i++)
    cin >> ci[i];
  sort(ci + 1, ci + N+1);
  for(int i = 1; i <= N; i++)
    if(in[i] == 1)
      q.push(i);
 
  int cur = 1;
  while(q.size()) {
    int here = q.front(); q.pop();
    ans[here] = ci[cur];
    sum += ci[cur++];
    for( int there : vt[here]) {
      in[there]--;
      in[here]--;
      if(in[there] == 1)
        q.push(there);
    }
  }
  sum -= ci[N];
  cout << sum << "\n";
  for(int i = 1; i <= N; i++)
    cout << ans[i] << " ";
}