[백준 7044] Bad Cowtractors

[ghdcksgml1]

Bessie has been hired to build a cheap internet network among Farmer John's N (2 <= N <= 1,000) barns that are conveniently numbered 1..N.

베시는 농부 존의 N개의 외양간(1부터 N까지 편리하게 넘버링이 되어있는) 사이에 인터넷 네트워크망을 싸게 설치하기 위해서 고용되었다.

FJ has already done some surveying, and found M (1 <= M <= 20,000) possible connection routes between pairs of barns.

농부 존은 이미 조사를 끝냈고, 외양간 쌍들 사이의 연결 가능한 루트들이 M개 인 것을 찾아냈다.

Each possible connection route has an associated cost C (1 <= C <= 100,000).

각각의 연결 가능한 루트는 비용이 C로 연결되어 있다.

Farmer John wants to spend the least amount on connecting the network; he doesn't even want to pay Bessie.

농부 존은 최소한의 네트워크 연결을 하기를 원한다. 그는 베시에게 돈을 지불하고 싶어하지도 않는다.

Realizing Farmer John will not pay her, Bessie decides to do the worst job possible.

농부 존이 그녀에게 결제를 하지 않을 것을 알아차려서, 베시는 가능한 최악의 결정을 할것이다.

She must decide on a set of connections to install so that (i) the total cost of these connections is as large as possible, (ii) all the barns are connected together (so that it is possible to reach any barn from any other barn via a path of installed connections), and (iii) so that there are no cycles among the connections (which Farmer John would easily be able to detect).

그녀는 하나의 연결들의 집합을 설치하는 것을 결정해야한다. (i) 연결들의 총 비용들을 가능한 크게하기 위해서,

(ii) 모든 외양간들을 함께 연결한다. (설치된 연결들의 길을 통해 다른 외양간에서 어떤 외양간에 도달할 수 있도록)

그리고 (iii) 연결들 사이에 사이클이 없도록 한다. ( 농부 존이 쉽게 감지할 수 있음 )

Conditions (ii) and (iii) ensure that the final set of connections will look like a "tree".

조건 (ii)와 (iii)는 최종 연결 집합이 트리형태일 것이 보장된다.

---

이 문제는 최소 스패닝 트리를 써서 푸는 문제입니다!

알고리즘 링크 : https://github.com/ghdcksgml1/Algorithm_Skill/blob/master/14_kruskalAlgorithm.cpp

보통은 최소 스패닝 트리를 통해 최소비용을 구하는 문제지만, 이 문제의 경우에는 베시가 심술이 나서

최소 스패닝 트리를 통해 최대비용을 구하는 문제입니다.

구현 자체는 최소 스패닝 트리로 최소비용을 구하는 문제에서 정렬부분만 살짝 바꿔주면 되지만 (원래 비용을 오름차순으로 정렬하지만, 이 문제에서는 내림차순으로 정렬하면 된다.) , 이 문제에서는 모든 외양간을 연결하지 못하는 경우가 발생할 수 있기 때문에 그 예외처리도 해줘야합니다.

---

// 언어 : C++ , (성공/실패) : 1/4 , 메모리 : 2732 KB , 시간 : 4ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset

using namespace std;
class Edge{
public:
    int node[2];
    int distance;
    Edge(int a,int b,int distance){
        this->node[0] = a;
        this->node[1] = b;
        this->distance = distance;
    }
};

int N,M;
vector<Edge> edge;
int parent[1001];
bool visit[1001];

// 부모 리턴
int getParent(int parent[], int x){
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x]);
}

// 부모를 공유한다.
void unionParent(int parent[], int a,int b){
    a = getParent(parent,a);
    b = getParent(parent, b);
    if(a<b) parent[b] = a;
    else parent[a] = b;
}

// 공통 부모를 찾는다.
int findParent(int parent[], int a,int b){
    a = getParent(parent,a);
    b = getParent(parent, b);
    if(a==b) return 1;
    return 0;
}

bool compare (Edge a,Edge b){
    return a.distance > b.distance;
}


int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b,c;
        cin>>a>>b>>c;
        edge.push_back(Edge(a,b,c));
    }

    sort(edge.begin(),edge.end(),compare); // 최소 스패닝 트리의 최댓값을 구하기 위해 distance가 높은 순으로 정렬
    for(int i=1;i<=N;i++){
        parent[i] = i;
    }
    int sum = 0;
    int cnt = 0; // cnt가 N-1이 나와야 모든 곳이 네트워크 연결된 것이다.
    for(int i=0;i<edge.size();i++){
        if(!findParent(parent,edge[i].node[0],edge[i].node[1])){
            sum += edge[i].distance;
            unionParent(parent,edge[i].node[0],edge[i].node[1]);
            cnt++;
        }
    }

    cout<<(cnt==N-1?sum:-1)<<'\n';

    return 0;
}

---

conveniently: 편리하게

reach: 도달하다

condition: 조건

set: 집합