[Algorithm] C++ 백준 16191번 : Utilitarianism

트리에서 서로 인접하지 않는 k개의 간선을 골라 가중치 합을 최대로 만드는 문제. 라그랑주 최적화(λ)로 k-제약을 벌점으로 흡수하고, 노드별 상태 DP(A/B)로 F(λ)=max∑(w-λ)와 선택 간선 수를 O(n)에 계산, λ에 대한 단조성을 이용해 이분 탐색 후 F(λ)+λk의 최소값으로 정답을 복원한다.

문제: BOJ 16191 - Utilitarianism

문제 요약

n개의 도시가 트리를 이루고, 간선마다 정수 가중치가 있다.
서로 정점(도시)을 공유하지 않도록 k개의 간선을 선택해 가중치 합을 최대화하라.
최대 매칭 크기 < k이면 Impossible.

핵심 아이디어 (라그랑주 최적화 + 트리 DP)

선택 간선 수 제약을 벌점 항으로 흡수: 임의의 실수 λ에 대해 F(λ) = max Σ (w_e - λ) 를 계산하면, 최적해의 간선 수 m(λ)는 λ가 커질수록 단조 감소한다.
정확히 k개를 고른 최대 합은 이중성으로 min_λ [ F(λ) + λ·k ] 로 복원된다.
트리 DP로 F(λ)와 m(λ)를 O(n) 계산:
- 상태 A(u): u가 부모와 매칭되지 않음 → 자식 중 최대 한 명과 매칭 가능.
- 상태 B(u): u가 부모와 매칭됨 → 자식과는 매칭 불가.
- 각 자식에 대해 A/B 전이값을 모으고, A(u)에서는 “한 자식과 매칭"의 이득 dpB[v] + (w-λ) - dpA[v] 중 최댓값만 취함.
- 동률 시 더 많은 간선을 선택하는 해를 우선해 단조성을 보장.
이분 탐색으로 m(λ) ≤ k가 처음 성립하는 최소 λ를 찾고, λ와 λ-1에서 F(λ)+λk의 최소값을 정답으로 사용.

시간 복잡도

run(λ)가 O(n), 이분 탐색 O(log W) → 전체 O(n log W).

C++ 구현

 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
// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

struct Pair { long long profit; int cnt; };

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k; if (!(cin >> n >> k)) return 0;
  vector<vector<pair<int,long long>>> g(n+1);
  for (int i = 0; i < n-1; ++i) {
    int u, v; long long c; cin >> u >> v >> c;
    g[u].push_back({v, c}); g[v].push_back({u, c});
  }

  // Rooting and order
  vector<int> parent(n+1, 0), order; order.reserve(n);
  vector<int> st; st.reserve(n); parent[1] = -1; st.push_back(1);
  while (!st.empty()) {
    int u = st.back(); st.pop_back(); order.push_back(u);
    for (auto &e : g[u]) {
      int v = e.first; if (v == parent[u]) continue;
      if (parent[v] != 0) continue; parent[v] = u; st.push_back(v);
    }
  }

  vector<long long> dpA(n+1, 0), dpB(n+1, 0);
  vector<int> cntA(n+1, 0), cntB(n+1, 0);

  auto better = [](const Pair &a, const Pair &b) {
    if (a.profit != b.profit) return a.profit > b.profit;
    return a.cnt > b.cnt; // tie-break: prefer larger count
  };

  auto run = [&](long long lambda) -> Pair {
    for (int idx = (int)order.size() - 1; idx >= 0; --idx) {
      int u = order[idx];
      long long baseProfit = 0; int baseCnt = 0;
      for (auto &e : g[u]) {
        int v = e.first; if (v == parent[u]) continue;
        baseProfit += dpA[v]; baseCnt += cntA[v];
      }
      Pair bestDelta{0, 0};
      for (auto &e : g[u]) {
        int v = e.first; if (v == parent[u]) continue; long long w = e.second;
        long long deltaProfit = dpB[v] + (w - lambda) - dpA[v];
        int deltaCnt = cntB[v] + 1 - cntA[v];
        Pair cand{deltaProfit, deltaCnt};
        if (better(cand, bestDelta)) bestDelta = cand;
      }
      // u matched with parent → cannot match children
      dpB[u] = baseProfit; cntB[u] = baseCnt;
      // u free → at most one child match
      dpA[u] = baseProfit + bestDelta.profit; cntA[u] = baseCnt + bestDelta.cnt;
    }
    return {dpA[1], cntA[1]};
  };

  const long long LAM_INF = 1000000000000LL; // 1e12
  Pair neg = run(-LAM_INF);
  if (neg.cnt < k) { cout << "Impossible\n"; return 0; }

  long long lo = -LAM_INF, hi = LAM_INF;
  while (lo < hi) {
    long long mid = (lo + hi) >> 1;
    Pair res = run(mid);
    if (res.cnt <= k) hi = mid; else lo = mid + 1;
  }
  long long lam = lo;

  // convex dual reconstruction
  Pair r1 = run(lam); long long ans1 = r1.profit + lam * 1LL * k;
  Pair r0 = run(lam - 1); long long ans0 = r0.profit + (lam - 1) * 1LL * k;
  long long ans = min(ans0, ans1);

  cout << ans << '\n';
  return 0;
}