[C++]白準10423号:電気が切れた
質問リンク
10423号:電気が切れた
問題の概要
一つの国に複数の発電所がある都市.この国では、一対の都市の間にケーブルを敷設することができます.ケーブルを取り付けることができる都市に対して設置費用を支払う場合、すべての都市が発電所に接続できる最低設置費用を求める.
方法
すべての頂点を最小限のコストで接続する必要があるため、最小生成ツリーを思い出すことができます.
しかし,この問題に対して,「最小生成木」の基本問題は「複数の発電所」とは異なる.この問題を解決する方法は簡単です.つまり、最小生成ツリーを作成する前に、発電所がある頂点を1つの頂点にマージします.
これは簡単な考えの部分で、700人余りの金貨2題があるが、正解率は70%を超えた.
私の場合、クルーズアルゴリズムを使用して実現しました.
コード#コード#
10423号:電気が切れた
問題の概要
一つの国に複数の発電所がある都市.この国では、一対の都市の間にケーブルを敷設することができます.ケーブルを取り付けることができる都市に対して設置費用を支払う場合、すべての都市が発電所に接続できる最低設置費用を求める.
方法
すべての頂点を最小限のコストで接続する必要があるため、最小生成ツリーを思い出すことができます.
しかし,この問題に対して,「最小生成木」の基本問題は「複数の発電所」とは異なる.この問題を解決する方法は簡単です.つまり、最小生成ツリーを作成する前に、発電所がある頂点を1つの頂点にマージします.
これは簡単な考えの部分で、700人余りの金貨2題があるが、正解率は70%を超えた.
私の場合、クルーズアルゴリズムを使用して実現しました.
コード#コード#
#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define MAX 1001
using namespace std;
struct Info {
int u, v, w;
};
int parent[MAX];
vector<Info> info;
bool compare(const Info& a, const Info& b) { return a.w < b.w; }
int Find(int a)
{
if (a == parent[a])
return a;
return parent[a] = Find(parent[a]);
}
void Union(int a, int b)
{
int pa = Find(a), pb = Find(b);
parent[pa] = pb;
}
int main(void)
{
FASTIO;
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
parent[i] = i;
vector<int> tmp;
for (int i = 0; i < k; i++)
{
int city;
cin >> city;
tmp.push_back(city);
}
for (int i = 1; i < tmp.size(); i++)
Union(tmp[0], tmp[i]);
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
info.push_back({ u, v, w });
}
sort(ALL(info), compare);
int res = 0;
for (auto& i : info)
if (Find(i.u) != Find(i.v))
res += i.w, Union(i.u, i.v);
cout << res << endl;
return 0;
}
Reference
この問題について([C++]白準10423号:電気が切れた), 我々は、より多くの情報をここで見つけました https://velog.io/@beclever/C-백준-10423번-전기가-부족해テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol