結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2025-04-14 11:09:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 125 ms / 2,000 ms |
コード長 | 2,853 bytes |
コンパイル時間 | 3,068 ms |
コンパイル使用メモリ | 209,064 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-04-14 11:09:23 |
合計ジャッジ時間 | 5,735 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h> // #include<atcoder/all> using namespace std; // using namespace atcoder; using ll = long long; using VI = vector<int>; using P = pair<int, int>; using Tuple = tuple<int, int, int>; constexpr int INF = 1001001001; constexpr ll LINF = 1001001001001001001ll; #define rep(i, n) for (ll i = 0; i < (int)(n); i++) #define rep2(i, k, n) for (ll i = k; i < (int)(n); i++) //クラスカル法 Union-Findで辺のコストが小さい順に頂点を連結していく //O(VlogV) ∵sortに時間がかかる /// @参考元 https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find class DSU{//AtCoderLibraryが使えないときはclassでDSUを自作 public: DSU() = default; explicit DSU(size_t n) : m_parentsOrSize(n, -1) {} int leader(int i){ if(m_parentsOrSize[i] < 0) return i; // 経路圧縮 return (m_parentsOrSize[i] = leader(m_parentsOrSize[i])); } void merge(int a, int b){ a = leader(a); b = leader(b); if(a != b){ //小さいほうが子になる if(m_parentsOrSize[a] > m_parentsOrSize[b]) swap(a, b); m_parentsOrSize[a] += m_parentsOrSize[b]; m_parentsOrSize[b] = a; } } bool same(int a, int b){ return (leader(a) == leader(b)); } int size(int i){ return -m_parentsOrSize[leader(i)]; } private: // m_parentsOrSize[i] は i の 親, // ただし root の場合は (-1 * そのグループに属する要素数) vector<int> m_parentsOrSize; }; bool fcomp(const Tuple& a, const Tuple& b){//sortの比較関数 auto&[h1, h2, wa] = a; auto&[h3, h4, wb] = b; return wa < wb;//Pair型の第二成分でsort } int main(){ ll ans = 0; int n, m, k; cin >> n >> m >> k; // vector<vector<int>> v(n, vector<int>(m)); vector<tuple<int,int,int>> edge(m), edge2; vector<bool> add(m, false); ll sum = 0; rep(i, m){ int s, t, w; cin >> s >> t >> w; s--, t--; edge[i] = make_tuple(s, t, w); sum += w; } DSU d(n); rep(i, k){ int e; cin >> e; e--; add[e] = true; auto[a, b, w] = edge[e]; sum -= w; d.merge(a, b); } // cout << sum << endl; rep(i, m){ if(!add[i]){ auto[a, b, w] = edge[i]; edge2.emplace_back(a, b, w); } } sort(edge2.begin(), edge2.end(), fcomp); for(auto[a, b, w]: edge2){ // cout << 'a' << a << " b" << b << " w" << w << endl; if(d.same(a, b)) continue; d.merge(a, b); sum -= w; } ans = sum; cout << ans << endl; }