白駿アルゴリズム10423号:電力不足

リンク

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

質問する

世界で最もGDPが高い西江の国では、ソフトウェアやハードウェア技術が最も高く、IT強国と呼ばれ、2015年から世界で最も生活に適した国の1位に選ばれた.
「暮らしのよい国」の1位に選ばれて以来、外国人の訪問者が増え、それに伴って電力使用率が増加し、電力不足が深刻化している.このため、西江大統領は最近開発されたNY発電所事業を行うことにした.発電所を建設する際に重要なのは、発電所の建物や都市に電力を供給するケーブルです.発電所は特定の都市に建設されているため、追加の費用はケーブルの設置に必要なすべての費用である.このプロジェクトの問題は、ケーブルを取り付けるコストが非常に高いため、最小限に抑えて、すべての都市に電力を供給することです.N都市とM都市を結ぶケーブルの情報とK都市にNY発電所が設置されている都市があれば、できるだけケーブル設置費用を使ってすべての都市の電力供給問題を解決しなければならない.重要なのは、どの都市も2つの発電所から電力を供給するのが無駄で、ケーブルで接続されている都市には1つの発電所しかない必要があります.次のFigure 1を見てください.9つの都市と3つのNY発電所(A、B、I)があり、都市ごとに接続された料金です.


この例では、すべての都市に電力を供給するために取り付けられたケーブルの最小コストは22であり、Figure 2の太い幹線で接続されたケーブルである.B都市はつながっている都市は一つもありませんが、発電所が設置されている都市は電力を供給できるので大丈夫です.

入力

第1行は都市の個数N(1≦N≦1000)と実装可能なケーブルの個数M(1≦M≦100000)、発電所の個数K(1≦K≦N)を与える.2行目は発電所を設置した都市の番号を示した.3行目から、M都市を接続するケーブルの情報がu,v,w付与される.これは、u都市とv都市を接続するケーブルの設置にwの費用がかかることを意味する.wは10000以下の整数である.

しゅつりょく

すべての都市に電力を供給するために、ケーブルを取り付ける最低コストを出力します.

入力と出力の例

プールコード（C++）

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define all(v) v.begin(), v.end()
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>;
using wector = vector<vector<int>>;
using tii = tuple<int,int,int>;

struct UnionFind {
	vector<int> parent, rank, cnt;
	UnionFind(int n) : parent(n), rank(n, 1), cnt(n, 1) {
		iota(parent.begin(), parent.end(), 0);
	}
	int Find(int x) {
		return x == parent[x] ? x : parent[x] = Find(parent[x]);
	}
	bool Union(int a, int b) {
		a = Find(a), b = Find(b);
		if (a == b) return false;
		if (rank[a] < rank[b]) swap(a, b);
		parent[b] = a;
		rank[a] += rank[a] == rank[b];
		cnt[a] += cnt[b];
		return true;
	}
};

int main() {
  fastio;
  int n,m,k; cin >> n >> m >> k;
  vi energy(k);
  vector<tii> e;
  UnionFind UF(n + 1);
  for(int i = 0; i < k; i++) cin >> energy[i];
  for(int i = 1; i < energy.size(); i++) UF.Union(energy[i - 1],energy[i]);
  for(int i = 0; i < m; i++){
    int a,b,c; cin >> a >> b >> c;
    e.pb({c,a,b});
  }
  sort(all(e));
  int cnt = 0,cost = 0;
  for(auto [c,a,b] : e){
    a = UF.Find(a),b = UF.Find(b);
    if(a == b) continue;
    UF.Union(a,b);
    cost += c;
    if(++cnt == n - 1) break;
  }
  cout << cost << "\n";
  return 0;
}

すべての都市が最低コストで発電所に接続しなければならないので、まず発電所を縛ります.
これは、ナビゲーション時にルートノードが異なる場合は接続するだけで、後続の幹線の重み付け値に基づいて昇順にソートするプロセスです.