boj 10423: 전기가 부족해

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

10423번: 전기가 부족해

두 노드가 서로 같은 그룹이거나 (i), 공장에 연결된 노드면 (ii), 해당 간선을(from,to,cost) kruscal 알고리즘으로 합산하지 않으면 된다. 

(i)은 Find(from)과 From(to)인 parent비교만 하면 금방인데, (ii)는 어떻게 해야할 것인가?

바로 공장이 연결됬는지 여부를 map으로 저장하면 된다. 물론 공장의 노드번호는 매우 클 수 있으므로, 항상 parent가 무엇인지만을 따지는 map[Find(x)] 방식으로 true를 저장해야 할 것이다. 가량 9와 3,4가 이미 서로 한 그룹인데, 9만 공장이면, 나중에 6을 직접적으로 4와 연결해야 할 때, 9와 4의 조상인 parent인 3이 공장과 연결됐고, 따라서 6과 3을 연결했다고 해야 할 것이다.

총 합산에 더하는 경우는 따라서 (i),(ii)의 정반대인 경우인, 서로 parent가 달라야하며, from, to 둘중 최소한 하나는 공장과 연결이 되어 있지 않아야 한다. 만약 한쪽이 공장에 연결되어있다면, 다른한쪽을 공장에 연결해주면 된다.

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int n,m,k,u,v,w,x,p[1001];
vector<int> elec;
vector<pair<int,pair<int,int>>> edge;

map<int,int> m_;

int Find(int x){
  if(p[x]==x) return x;
  return p[x] = Find(p[x]);
}

void Union(int x, int y){
  int x1=p[x], y1=p[y];
  if(x1<y1){
    p[y1]=x1;
    Find(y);
  }else{
    p[x1]=y1;
    Find(x);
  }
  return;
}

int main(){

  cin>>n>>m>>k;
  for(int i=0;i<k;i++){
    cin>>x;
    m_[x]=1;
    elec.push_back(x);
  }
  for(int i=0;i<m;i++){
    cin>>u>>v>>w;
    edge.push_back({w,{u,v}});
    edge.push_back({w,{v,u}});
  }

  for(int i=1;i<=n;i++) p[i]=i;
  sort(edge.begin(),edge.end());
  ll ans=0;
  for(auto &e:edge){
    int cost=e.first, from=e.second.first, to=e.second.second;
    if(Find(from)!=Find(to)&&(!m_[Find(from)]||!m_[Find(to)])){
      if(m_[Find(from)]){
        m_[Find(to)]=1;
      }
      if(m_[Find(to)]){
        m_[Find(from)]=1;
      }
      ans+=cost;
      Union(from,to);
    }
  }
  cout<<ans<<'\n';

  return 0;
}

이것 말고도 그냥 차라리 공장들의 노드번호를 0으로 해서 하는 방법도 있다.

이건 머리가 좋다..