結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2018-10-19 22:23:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 3,471 bytes |
コンパイル時間 | 2,212 ms |
コンパイル使用メモリ | 187,188 KB |
実行使用メモリ | 15,720 KB |
最終ジャッジ日時 | 2024-11-18 21:14:22 |
合計ジャッジ時間 | 4,466 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;/* macro */#define rep(i,a,b) for(int i=a;i<b;i++)#define revrep(i,a,b) for(int i = a; i > b; i--)#define int long long#define exist(s,e) ((s).find(e)!=(s).end())#define all(v) (v).begin(), (v).end()#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)#define sum(v) accumulate(all(v), (0LL))/* alias */template<class T> using vec = vector<T>;typedef vector<int> vi;typedef pair<int, int> pi;/* constant */const int inf = 100100100100100100;const int mod = 1e9;int dx[8]={1,0,-1,0,-1,1,-1,1};int dy[8]={0,1,0,-1,-1,-1,1,1};/* io_method */int input(){int tmp;cin >> tmp;return tmp;}string raw_input(){string tmp;cin >> tmp;return tmp;}string readline(){string s;getline(cin, s);return s;}template<class T> void printx(T n){cout << n;}template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}template<class T> void print(T n){printx(n);cout << endl;}template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" <<endl;}/* general_method */template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }vector<int> cs(vector<int> arr){vector<int> tmp;if(arr.size() == 0) return tmp;tmp.push_back(arr[0]);rep(i,1,arr.size()){tmp.push_back(tmp.back() +arr[i]);}return tmp;}/* main */struct UnionFind {vector<int> par; // 親ノードvector<int> rank; // ランクUnionFind(int n = 1) {init(n);}void init(int n = 1) {par.resize(n); rank.resize(n);for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0;}int root(int x) {if (par[x] == x) {return x;}else {int r = root(par[x]);return par[x] = r;}}bool issame(int x, int y) {return root(x) == root(y);}bool merge(int x, int y) {x = root(x); y = root(y);if (x == y) return false;if (rank[x] < rank[y]) swap(x, y);if (rank[x] == rank[y]) ++rank[x];par[y] = x;return true;}int count_connected_comp(){set<int> s;rep(i,0,par.size()){s.insert(par[i]);}return s.size();}};signed main(){cin.tie(0);ios::sync_with_stdio(false);int n, m, e; cin >> n >>m >> e;vec<vi> edges;int costsum = 0;rep(i,0,m){int f,t, c; cin >> f >> t >> c; f--; t--;edges.push_back({c,i,f,t});}UnionFind uf = UnionFind(n);set<int> s;rep(i,0,e){int edg = input() - 1;uf.merge(edges[edg][2], edges[edg][3]);s.insert(edg);}sort(all(edges));rep(i,0,m){if(not exist(s, edges[i][1])){if(uf.issame(edges[i][2], edges[i][3])){costsum += edges[i][0];}else{uf.merge(edges[i][2], edges[i][3]);}}}print(costsum);}