백준 25545 - MMST (C++)

문제

• 문제 링크

  
   BOJ 25545 - MMST 
  

• 문제 요약

모든 간선의 가중치가 다른 무향 연결 그래프가 주어진다.
이 그래프의 $MMST$를 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 200,000$

$N - 1 ≤ M ≤ 500,000$

$-10^9 ≤ C_i ≤ 10^9$

알고리즘 분류

• 그래프 이론(graphs)
• 최소 스패닝 트리(minimum spanning tree)

풀이

얼핏 잘못 보면 삽질하기 쉬운 문제인데, $mst$의 본질을 안다면 굉장히 쉬워진다.

"모든 간선의 가중치가 다른 무향 연결 그래프가 주어질 때,"

위 조건을 유의한 채 얻을 수 있는 정보를 나열하면 다음과 같다.

• $M == N - 1$일 때는 $MMST$가 존재할 수 없다.
• 반대로 $N ≤ M$인 경우에는 서로 다른 스패닝 트리가 최소 $3$개 이상 존재한다.
• $Minimum$ $Spanning$ $Tree$와 $Maximum$ $Spanning$ $Tree$의 비용은 유일하다.
• 즉, $MMST$는 반드시 존재한다.

---

이제 문제는 다양하게 풀이해 볼 수 있다.
나는 다음의 과정대로 풀이하였다.

$N ≤ M$라는 가정 하에 $Minimum$ $Spanning$ $Tree$를 구성 해보자.
그럼 여기에 포함 되지 않는 간선이 적어도 하나 존재하게 되고,

이 간선 중 아무거나 하나를 반드시 포함한 채 다시 $Minimum$ $Spanning$ $Tree$를 구성해 보면 이것은 반드시 $MMST$가 된다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
struct E
{
    int p, q, w, i;
    bool operator<(E& e) { return w < e.w; }
}temp, Eg[500001];
int n, m, P[200001], an[200001];
 
int Find(int p) { return P[p] = P[p] == p ? p : Find(P[p]); }
void Merge(int p, int q) { P[p] > P[q] ? P[p] = q : P[q] = p; }
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i{}; i < m; i++)
        cin >> Eg[i].p >> Eg[i].q >> Eg[i].w, Eg[i].i = i + 1;
    sort(Eg, Eg + m);
}
void Solve(int o)
{
    if (n - 1 == m) cout << "NO", exit(0);
    iota(P, P + 200001, 0);
    if(o) an[0] = temp.i, Merge(temp.p, temp.q);
    for (int i{}, j{}; i < m; i++)
        if (int x(Find(Eg[i].p)), y(Find(Eg[i].q)); x ^ y)
        {
            Merge(x, y);
            if (o) an[++j] = Eg[i].i;
        }
        else temp = Eg[i];
    if (o) for (cout << "YES\n", m = 0; m < n - 1; cout << an[m++] << ' ');
}
int main()
{
    Init();
    Solve(0);
    Solve(1);
}

comment

끝