結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2019-02-19 21:53:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 2,016 bytes |
コンパイル時間 | 1,122 ms |
コンパイル使用メモリ | 104,512 KB |
実行使用メモリ | 11,340 KB |
最終ジャッジ日時 | 2024-10-12 21:30:54 |
合計ジャッジ時間 | 4,615 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include <cstdlib>#include <cmath>#include<cctype>#include<string>#include<set>#include <map>#include<algorithm>#include <functional>#include<vector>#include<climits>#include<stack>#include<queue>#include <deque>#include <typeinfo>#include <utility>#define rep(i,m,n) for(int i = m;i < n;++i)using namespace std;using ll = long long;using R = double;const ll inf = 1LL << 50;const ll MOD = 1e9 + 7;struct edge { ll to; ll from; ll cost; };bool comp(const edge& e1, const edge& e2) {return e1.cost < e2.cost;}ll V, E;class UnionFind {public:vector<int> r, p;UnionFind() {}UnionFind(int size) {r.resize(size, 0);p.resize(size, 0);rep(i, 0, size)makeSet(i);}void makeSet(int x) {p[x] = x;r[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 (r[x] > r[y]) {p[y] = x;}else {p[x] = y;if (x == y) {r[y]++;}}}int findSet(int x) {if (x == p[x]) {return x;}else {return p[x] = findSet(p[x]);}}};ll kruskal(vector<edge>edges,vector<pair<ll,ll>>should_unite) {sort(edges.begin(), edges.end(),comp);UnionFind un = UnionFind(V);rep(i, 0, should_unite.size()) {un.unite(should_unite[i].first,should_unite[i].second);}ll res = 0;rep(i, 0, edges.size()) {edge e = edges[i];if (!un.same(e.from, e.to)) {un.unite(e.from, e.to);res += e.cost;}}return res;}int main() {int K;cin >> V >> E >> K;vector<edge>edges;vector<pair<ll,ll>>should_unite;ll sum_1 = 0LL;ll sum_2 = 0LL;rep(i, 0, E) {ll a, b, c;cin >> a >> b >> c;a--; b--;sum_1 += c;edges.push_back({a,b,c});}rep(i, 0, K) {ll e;cin >> e;e--;sum_2 += edges[e].cost;should_unite.push_back({edges[e].from,edges[e].to});}cout << sum_1 - sum_2 - kruskal(edges, should_unite) << endl;}