[Codeforces 1081D] Maximum Distance

[Codeforces 1081D] Maximum Distance -1800

문제 설명 : 

n개의 vertex와 그 중에서 k개의 special vertex를 가지는 그래프가 주어진다. 문제는 각 special vertex간의 최장거리를 구하면 되는데, 이 문제 내에서 정의하는 '거리'란 edge들의 가중치의 합이 아닌 edge들의 가중치 중에서 가장 큰 값을 거리라고 정의한다. 예를 들어서 1->2로 가는데 가중치가 10, 2->3으로 가는데 가중치가 20이라면 1->3으로 가는 거리는 30이 아닌 20이 되는 것이다.

풀이 : 

이 문제는 MST(minimum spanning tree)로 풀면 된다. 즉 edge의 가중치를 오름차순으로 정렬한 뒤, special vertex가 모두 connected될 때까지 계속 연결한다. 그러다가 모두 connected되는 순간 그 때 해당하는 edge의 가중치가 정답이 된다(모든 special vertex에 대하여). 이 문제에서는 '거리'라는 개념을 특별하게 정의하고 있다. 가중치들의 합이 아닌 가중치들 중에서 가장 큰 가중치가 거리가 되므로 내가 거리를 구하기 위해서 필요한 것은 special vertex끼리 모두 connected되게 만드는 edge중에서 가장 가중치가 큰 edge 딱 하나만 알면 되는 것이다. 나머지 edge들은 그보다 작을 것이므로 답에는 아무런 상관이 없다. 노드들을 최소비용으로 connected 되도록 만드는 알고리즘이 바로 MST라고 생각하면 된다.

주의할 점 : 

노드들을 merge해나가는 과정에서 언제 special vertex들이 모두 connected 되었는지 판단해야하는 문제가 있다. 그 방법은 집합 안에 special vertex가 몇 개 들어있는지를 따로 저장해놓는 것이다. 그러면 a노드와 b노드를 merge하는 과정에서 (a와 b가 disjoint상태라면) 두 노드의 special vertex의 개수를 더해주면 된다. 더한 개수가 총 special vertex의 개수(=k)와 같아지면 모두 connected 되었다고 판단하면 된다. 이에 대한 구현은 아래 코드의 64~66줄에 나와있고, 이를 저장하는 변수는 good_cnt[]이다.

배운 점 : 

MST로 푸는 줄 알면 금방 풀 수 있는 문제인데 그걸 생각해내기가 어려웠다. MST는 특정 노드들을 최소 cost를 사용해서 모두 connected 되도록 만드는데 사용한다. 이 문제가 거기에 해당된다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 100009;
 
vector<pii> graph[SIZE];
vector<pair<int,pii>> edge;
int p[SIZE],good_cnt[SIZE]={0};
 
bool pii_cmp(const pair<int,pii> &A,const pair<int,pii> &B){
    return A.second.second<B.second.second;
}
int find(int a){
    if(p[a]==-1) return a;
    return p[a]=find(p[a]);
}
 
int merge(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return 0;
    p[b]=a;
    good_cnt[a]+=good_cnt[b];
    good_cnt[b]=0;
    return good_cnt[a];
}
 
int main(){
    int n,m,k;  scanf("%d %d %d",&n,&m,&k);
 
    for(int i=1 ; i<=k ; i++){
        int inp;    scanf("%d",&inp);
        good_cnt[inp]=1;
    }
 
    for(int i=1 ; i<=m ; i++){
        int u,v,c;  scanf("%d %d %d",&u,&v,&c);
        graph[u].push_back({v,c});
        graph[v].push_back({u,c});
        edge.push_back({u,{v,c}});
    }
 
    for(int i=1 ; i<=n ; i++) p[i]=-1;
 
    sort(edge.begin(),edge.end(),pii_cmp);
 
    int ans,cnt=0;
    for(auto &here:edge){
        int cur=here.first,to=here.second.first,cost=here.second.second;
 
        if(find(cur)!=find(to)){
            int cur_cnt=merge(cur,to);
            
            if(cur_cnt==k){
                ans=cost;
                break;
            }
        }           
    }
    for(int i=0 ; i<k ; i++)
        printf("%d ",ans);
    
    return 0;
}