結果

問題 No.748 yuki国のお財布事情
ユーザー matsukin1111matsukin1111
提出日時 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0