184.ネットワーク
34225 ワード
白駿
1. Python
クルーズアルゴリズム
n = int(input())
m = int(input())
parent = [i for i in range(n + 1)]
edges = []
def find(x):
if(parent[x] == x): return x
parent[x] = find(parent[x])
return parent[x]
def union(a,b):
a = find(a)
b = find(b)
if not a == b:
parent[b] = a
def check(a,b):
if find(a) == find(b):
return True
else:
return False
for _ in range(m):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
edges.sort()
result = 0
for edge in edges:
cost, a, b = edge
if not check(a, b):
union(a, b)
result += cost
print(result)
プリフェッチアルゴリズム
import sys
import heapq
def prim(v):
q = []
mst[v] = 1
result = 0
for i in adj[v]:
heapq.heappush(q, i)
while q:
c, v = heapq.heappop(q)
if not mst[v]:
mst[v] = 1
result += c
for j in adj[v]:
heapq.heappush(q, j)
if sum(mst) == n:
return result
input = sys.stdin.readline
n = int(input())
m = int(input())
adj = [[] for _ in range(n+1)]
mst = [0]*(n+1)
for _ in range(m):
a, b, c = map(int, input().split())
adj[a].append([c, b])
adj[b].append([c, a])
print(prim(1))
2. C++
クルーズアルゴリズム
#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 0x7fff0000
#define N_ 100000
using namespace std;
int n, m, par[N_], ans;
vector<pair<int, pair<int, int>>> v;
int find(int x) {
if (x == par[x])
return x;
return par[x] = find(par[x]);
}
bool Merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y)
return false;
par[y] = x;
return true;
}
int main() {
int v1, v2, w;
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
par[i] = i;
while (m--) {
cin >> v1 >> v2 >> w;
v.push_back({ w, {v1, v2}});
}
sort(v.begin(), v.end()); // 가중치 별 정렬
for (int i = 0; i < v.size(); i++) {
int w = v[i].first;
int v1 = v[i].second.first;
int v2 = v[i].second.second;
if (Merge(v1, v2)) // 사이클 발생하지 않을경우 연결 후
ans += w; // 연결비용 적재
}
cout << ans;
return 0;
}
プリフェッチアルゴリズム
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
const int INF = 2000000000;
int n, m;
vector <pair<int, int>> vec[1001];
vector <pair<int, int>> selected;
bool visited[1001] = { 0, };
int result = 0;
void prim() {
priority_queue <pair<int, int>> pq;
for (int i = 0; i < vec[1].size(); i++) {
int to = vec[1][i].first;
int co = vec[1][i].second;
pq.push(make_pair(-1 * co, to));
}
visited[1] = 1;
while (!pq.empty()) {
int co = pq.top().first * -1;
int to = pq.top().second;
pq.pop();
if (visited[to] == false) {
visited[to] = true;
result += co;
for (int i = 0; i < vec[to].size(); i++) {
int nto = vec[to][i].first;
int nco = vec[to][i].second;
if(visited[nto] == false)
pq.push(make_pair(-1 * nco, nto));
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
cin >> m;
int from, to, cost;
for (int i = 0; i < m; i++) {
cin >> from >> to >> cost;
vec[from].push_back(make_pair(to, cost));
vec[to].push_back(make_pair(from, cost));
}
prim();
cout << result << endl;
return 0;
}
Reference
この問題について(184.ネットワーク), 我々は、より多くの情報をここで見つけました https://velog.io/@corone_hi/184.-네트워크テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol