[13418] 학교 탐방하기

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

으악..한 10번 틀렸네요...

문제를 잘읽읍시다..!

블록친 부분을 굉장히! 아주 잘 읽으셔야합니다.

저는 저 부분을 안읽고.. 내가 내려갈떄 내리막길이면 올라올떈 오르막길이니 어느방향에서 접근하냐에 따라 달라질 것이라고 생각했습니다.

삐삐!!!!!!!!

아니였습니다.

이 문제는 그냥 연결해라!!!!!!!!!!!!! 이 문제였습니다...

네!

MST.. 최소 스패닝 트리로 해결하는 문제입니다.

저는 크루스칼로 해결했습니다.

MST에는 크루스칼과 프림이 있는데 MST를 잘모르시는 분들은

공부를 하고 문제를 해결하시기 바랍니당!

간단하게 설명해드리자면! 싸이클이 생기지 않고 정점 n개를 간선 n - 1개로 연결하는 방법입니당!

크루스칼에서는 disjoint-set 알고리즘이 사용됩니당!

성능을 위해서는 우선순위-큐를 사용하시면 더 도움이 됩니다.!

이 문제는 input에서 오르막길이 0으로, 내리막길이 1로 들어오니 조심하셔서 푸십시용!

아래는 코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 0x7fffffff
#define MOD 10000
#define MAX_SIZE 1001
#define mp make_pair
#define pii pair<int, int>
//ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
 
int parent[MAX_SIZE];
int n, m;
vector<pair<pii, int> > edge;
 
int find(int x) {
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}
 
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[x] = y;
        return 1;
    }
 
    return 0;
}
 
int f(int mul) {
    priority_queue<pair<int, pii> > pq;
 
    for (int i = 0; i <= n; i++) parent[i] = i;
 
    for (int i = 0; i < edge.size(); i++) pq.push(mp(!edge[i].second * mul, mp(edge[i].first.first, edge[i].first.second)));
 
    int ret = 0;
    int cnt = 0;
 
    while (!pq.empty() && cnt <= n - 1) {
        int k = pq.top().first * mul;
        int from = pq.top().second.first;
        int to = pq.top().second.second;
        pq.pop();
 
        bool tmp = merge(from, to);
        if (tmp) {
            cnt++;
            ret += k;
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < m + 1; i++) {
        int a, b;
        bool c;
        cin >> a >> b >> c;
 
        edge.push_back(mp(mp(a, b), c));
    }
 
    int best = f(-1);
    int worst = f(1);
 
    cout << worst*worst - best*best;
 
    return 0;
}