학교 탐방하기 (feat. 백준, 13418번)

학교 탐방하기
https://www.acmicpc.net/problem/13418

13418번: 학교 탐방하기

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M;
bool visit[1001];
vector<pair<int, int>> arr[1001];
int worst_case(){
    memset(visit, false, N + 1);
    register int ans = 0;
    priority_queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    while(!q.empty()){
        auto next = q.top().second, cost = q.top().first, nnext = 0; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        if(cost == 1)
            ++ans;
        for(auto& v : arr[next]){
            nnext = v.first, cost = v.second;
            if(!visit[nnext])
                q.push(make_pair(cost, nnext));
        }
    }
    return ans * ans;
}
int best_case(){
    memset(visit, false, N + 1);
    register int ans = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, 0));
    while(!q.empty()){
        auto next = q.top().second, cost = q.top().first, nnext = 0; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        if(cost == 1)
            ++ans;
        for(auto& v : arr[next]){
            nnext = v.first, cost = v.second;
            if(!visit[nnext])
                q.push(make_pair(cost, nnext));
        }
    }
    return ans * ans;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> M;
    for(register int m = 0, a, b, c; m <= M; ++m){
        cin >> a >> b >> c;
        if(c == 0)
            c = 1;
        else
            c = 0;
        arr[a].push_back(make_pair(b, c)), arr[b].push_back(make_pair(a, c));
    }
    cout << worst_case() - best_case();
    return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 구하는 문제입니다.

프림 알고리즘을 활용하여 풀이하였습니다.

문제의 트릭은 입구가 1번과'만' 연결되어 있는 것은 아니라는 것입니다.

두번째 줄은 입구와 1번과의 연결 관계가 항상 표기됩니다.

하지만 세번째 줄부터 입구와 N번과의 연결 관계가 표기될 수도 있습니다.