Back Junアルゴリズム1922:ネットワーク接続

リンク

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

質問する

道賢はコンピューターとコンピューターを接続するネットワークを構築しなければならない.しかし残念なことに、ハブがなく、コンピュータとコンピュータを直接接続する必要があります.しかし、みんなが資料を共有するために、すべてのパソコンがつながっています.(aとbの接続はaとbの経路が存在することを意味する.aとbには接続線があり、bとcには接続線があり、aとcには接続線がある.)
しかし、コンピューターに接続する費用を最小限に抑える以上、コンピューターに接続する費用のほかに、他の場所にお金を使うこともできます.これにより、各コンピュータへの接続に必要なコストが達成されると、すべてのコンピュータへの接続に必要な最低コストが出力されます.接続できないパソコンは1台もありません.

入力

第1行は、計算機数N(1≦N≦1000)を与える.
2行目は、接続可能な直線数M(1≦M≦100000)を与える.
3行目からM+2行目まで、各コンピュータをM行に接続するのに必要な費用.この費用の情報は3つの整数であり、a b cが与えられた場合、aコンピュータとbコンピュータを接続する費用はc(1≦c≦10000)であることを示す.aとbは同じかもしれません.

しゅつりょく

すべてのコンピュータを接続するために必要な最小コストを最初のローに出力します.

入力と出力の例

プールコード（C++）

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MAX 100001
#define INF 1e9+7
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
#define sz(a) int((a).size())

int root[MAX];

void init(int n){
  for(int i = 0; i <= n; i++) root[i] = i;
}

int find(int x){
  if(root[x] == x) return x;
  return root[x] = find(root[x]);
}

bool Union(int x,int y){
  x = find(x), y = find(y);
  if(x == y) return false;
  root[x] = y;
  return true;
}

struct Edge{
  int u,v,w;
  Edge(): Edge(-1, -1, 0){}
  Edge(int u1,int v1, int w1): u(u1),v(v1),w(w1){}
  bool operator < (const Edge& O)const{ return w < O.w; };
};

int main(){
  fastio;
  int n,m; cin >> n >> m;
  Edge e[MAX];
  init(n);
  for(int i = 0; i < m; i++){
    int a,b,c; cin >> a >> b >> c;
    e[i] = Edge(a-1,b-1,c);
  }
  sort(e, e + m); // 간선을 가중치를 기준으로 오름차순 정렬
  // result : 가중치 합, cnt : 뽑은 간선의 수
  int result = 0, cnt = 0;
  for(int i = 0; ; i++){
    if(Union(e[i].u, e[i].v)){
      result += e[i].w;
      if(++cnt == n - 1) break; // n - 1개의 간선을 뽑으면 나감.(MST)의 조건
    }
  }
  cout << result;
  return 0;
}