結果

問題 No.748 yuki国のお財布事情
ユーザー matsukin1111
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;

}
0