학교 탐방하기 - 13418

//13418 - 학교 탐방하기
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
vector<pair<int, int>> up;
vector<pair<int, int>> down;
 
struct DisjointSet
{
    vector<int> parent, rank;
 
    DisjointSet(int n) : parent(n), rank(n, 1)
    {
        for(int i = 0; i<n; ++i)
            parent[i] = i;
    }
 
    int find(int u)
    {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
 
    void merge(int u, int v)
    {
        u = find(u), v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) ++rank[v];
    }
};
 
void init()
{
    cin >> N >> M;
    ++N;
    int x, y, flag;
    for(int i = 0; i<=M; ++i)
    {
        cin >> x >> y >> flag;
        if(flag)
            down.push_back(make_pair(x, y));
        else
            up.push_back(make_pair(x, y));
    }
}
 
int prim(DisjointSet& set, vector<pair<int, int>>& V)
{
    int ret = 0;
    for(int i = 0; i<V.size(); ++i)
    {
        int u = V[i].first;
        int v = V[i].second;
        if(set.find(u) == set.find(v)) continue;
        ++ret;
        set.merge(u, v);
    }
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    DisjointSet set(N);
 
    int u = prim(set, up);
    DisjointSet set2(N);
    prim(set2, down);
    int v = prim(set2, up);
    cout << u*u - v*v;
}

 

 

 

 

 

 

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

13418번: 학교 탐방하기

 

 

 

 

 

 

학교 탐방하기

스패닝 트리중 오르막이 가장 많이 포함된것과 오르막이 가장 적게 포함된것의 차이를 묻는 문제입니다.

프림알고리즘을 이용하여 해결할수 있었습니다.