結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2018-10-19 22:18:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 159 ms / 2,000 ms |
コード長 | 1,934 bytes |
コンパイル時間 | 1,030 ms |
コンパイル使用メモリ | 89,268 KB |
実行使用メモリ | 9,680 KB |
最終ジャッジ日時 | 2024-11-18 21:08:16 |
合計ジャッジ時間 | 3,421 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<set>using namespace std;typedef long long ll;struct Edge{int from , to, cost;Edge() {}Edge(int f, int t, int c) : from(f), to(t), cost(c) {}bool operator<(const Edge other) const{return cost < other.cost;}};class DisjointSet{public:vector<int> rank, p;DisjointSet(){}DisjointSet(int size){rank.resize(size, 0);p.resize(size, 0);for(int i = 0; i < size; i++) makeSet(i);}void makeSet(int x){p[x] = x;rank[x] = 0;}bool same(int x, int y){return findSet(x) == findSet(y);}void unite(int x, int y){link(findSet(x), findSet(y));}void link(int x, int y){if(rank[x] > rank[y]){p[y] = x;}else{p[x] = y;if(rank[x] == rank[y]){rank[y]++;}}}int findSet(int x){if(x != p[x]){// path compressionp[x] = findSet(p[x]);}return p[x];}};int main(){int n, m, k, a, b, c, e;cin >> n >> m >> k;vector<Edge> v;for(int i = 0; i < m; i++){cin >> a >> b >> c;a--, b--;v.push_back(Edge(a, b, c));}set<int> save;for(int i = 0; i < k; i++){cin >> e;e--;save.insert(e);}DisjointSet uf(n);vector<Edge> mst;for(int i = 0; i < m; i++){if(save.count(i) == 0) mst.push_back(v[i]);else uf.unite(v[i].from, v[i].to);}sort(mst.begin(), mst.end());ll ans = 0;for(int i = 0; i < mst.size(); i++){if(!uf.same(mst[i].from, mst[i].to)){uf.unite(mst[i].from, mst[i].to);}else{ans += mst[i].cost;}}cout << ans << endl;return 0;}