BOJ 27498 - 연애 혁명

BOJ 27498 - 연애 혁명

$K$각 관계가 없다는 것은 싸이클이 없다는 것이므로 최대로 간선을 남기기 위해 트리 모양이 만들어짐을 알 수 있다.

$d=0$ 인 간선들에 대해 모아두고 $c$ 가 큰 순서대로 간선을 이어줘야 포기하도록 만든 애정도가 최소가 되게 할 수 있다.

모든 간선의 가중치 - $d=1$ 인 간선의 가중치 - 트리를 만들기 위해서 이은 $d=0$ 인 간선들의 가중치가 정답이다.

struct DSU {
   vector<int> p;
   DSU(int n) : p(n, -1) {}
   int gp(int n) {
      if (p[n] < 0) return n;
      return p[n] = gp(p[n]);
   }
   void merge(int a, int b, int to_b = 0) {
      a = gp(a), b = gp(b);
      if (a == b) return;
      if (!to_b && size(a) > size(b)) swap(a, b);
      p[b] += p[a];
      p[a] = b;
   }
   bool is_merged(int a, int b) { return gp(a) == gp(b); }
   int size(int n) { return -p[gp(n)]; }
};
void solve() {
   int n, m;
   cin >> n >> m;
   ll tot = 0;
   ll included = 0;
   vector<array<int, 3>> edges;
   DSU dsu(n);
   for (int i = 0; i < m; i++) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      a--, b--;
      tot += c;
      if (d == 1) {
         included += c;
         dsu.merge(a, b);
      } else {
         edges.pb({c, a, b});
      }
   }
   sort(all(edges), greater<>());
   for (auto &[c, a, b]: edges) {
      if (!dsu.is_merged(a, b)) {
         dsu.merge(a, b);
         included += c;
      }
   }
   cout << tot - included;
}