1일1알

백준 13905번 세부 C++ 본문

알고리즘

백준 13905번 세부 C++

영춘권의달인 2022. 10. 31. 15:39

https://www.acmicpc.net/problem/13905

 

13905번: 세부

첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄

www.acmicpc.net

 

최소 스패닝 트리 응용해서 최대 스패닝 트리

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m, s, e;
int ans = 0;

struct Info {
    int start;
    int end;
    int weight;

    bool operator<(const Info& other) {
        return weight < other.weight;
    }
    bool operator>(const Info& other) {
        return weight > other.weight;
    }
};

vector<int> parent;
vector<int> height;
vector<Info> infos;

int GetParent(int n) {
    if (n == parent[n]) return n;
    return parent[n] = GetParent(parent[n]);
}

void Merge(int u, int v) {
    u = GetParent(u);
    v = GetParent(v);
    if (u == v) return;

    if (height[u] > height[v])
        ::swap(u, v);

    parent[u] = v;

    if (height[u] == height[v])
        height[v]++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m >> s >> e;
    parent = vector<int>(n + 1);
    height = vector<int>(n + 1, 1);
    for (int i = 1; i <= n; i++) parent[i] = i;

    for (int i = 0; i < m; i++) {
        int start, end, weight;
        cin >> start >> end >> weight;
        infos.push_back({ start,end,weight });
    }
    sort(infos.begin(), infos.end(), greater<>());
    bool isPossible = false;
    int ans = -1;
    for (auto a : infos) {
        if (GetParent(a.start) == GetParent(a.end)) continue;
        Merge(a.start, a.end);
        ans = a.weight;
        if (GetParent(s) == GetParent(e)) {
            isPossible = true;
            break;
        }
    }
    if (!isPossible) cout << 0;
    else cout << ans;
}
저작자표시

'알고리즘' 카테고리의 다른 글

백준 1245번 농장 관리 C++  (0) 2022.11.03
백준 17178번 줄서기 C++  (0) 2022.11.02
백준 2109번 순회강연 C++  (0) 2022.10.30
백준 15789번 CTP 왕국은 한솔 왕국을 이길 수 있을까? C++  (1) 2022.10.29
백준 25195번 Yes or yes C++  (0) 2022.10.28
'알고리즘' Related Articles more