結果
問題 |
No.748 yuki国のお財布事情
|
ユーザー |
|
提出日時 | 2018-12-16 21:33:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 135 ms / 2,000 ms |
コード長 | 1,572 bytes |
コンパイル時間 | 2,281 ms |
コンパイル使用メモリ | 178,872 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-09-25 06:36:58 |
合計ジャッジ時間 | 5,791 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; // one-based numbering struct union_find { vector<int> data; // i: (data[i] < 0) -> group size, (data[i] > 0) -> parent; union_find(int n) { data.resize(n+1, -1); } int find(int x) { if(data[x] < 0) return x; else return data[x] = find(data[x]); } int size(int x) { return -data[find(x)]; } void unite(int x, int y) { x = find(x); y = find(y); if(x == y) return; if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; } bool same(int x, int y) { x = find(x); y = find(y); return x == y; } }; template<class Numeric> struct edge { int from, to; Numeric cost; bool operator< (struct edge &e) { return cost < e.cost; } }; template<class Numeric> Numeric kruskal(int n, vector< edge<Numeric> > v, union_find u) { sort(v.begin(), v.end()); Numeric mincost = 0; for (int i = 0; i < v.size(); i++) { if (!u.same(v[i].from, v[i].to)){ mincost += v[i].cost; u.unite(v[i].from, v[i].to); } } return mincost; } int main(){ int n, m, k; cin >> n >> m >> k; vector< edge<long long> > v(m); long long ans = 0; for (int i = 0; i < m; ++i) { cin >> v[i].from >> v[i].to >> v[i].cost; ans += v[i].cost; } union_find u(n); for (int i = 0; i < k; ++i) { int c; cin >> c; c--; u.unite(v[c].from, v[c].to); ans -= v[c].cost; } cout << ans - kruskal(n, v, u) << endl; return 0; }