최단거리 문제이지만 일종의 MST구조이다.
아래의 두 알고리즘은 사용하지 않지만 다익스트라 알고리즘으로
세 지점에서의 거리를 계산하여 최소가 되는 지점을 찾는다.
그 지점이 결국 세 지점을 연결할 수 있는 중점이 된다.
<Prim Algorithm>
//Prim algorithm
#include <cstdio>
#include <queue>
#include <functional>
#include <vector>
using namespace std;
#define mp(a,b) make_pair(a,b)
typedef pair<int, int> P;
int V, E;
int visit[10001];
int dist[10001];
vector<P> vec[10001];
int Prim(int start){
int ans = 0;
priority_queue < P, vector<P>, greater < P > > pq;
pq.push(mp(0, start)); //가중치, 시작지점
while (!pq.empty()){
int val = pq.top().first;
int from = pq.top().second;
pq.pop();
if (visit[from]) continue;
visit[from] = 1;
dist[from] = val;
ans += dist[from];
for (int i = 0; i < vec[from].size(); i++){
int nval = vec[from][i].first;
int to = vec[from][i].second;
if (visit[to]) continue;
pq.push(mp(nval, to));
}
}
return ans;
}
int main(){
int a, b, c;
scanf("%d%d", &V, &E);
for (int n = 0; n < E; n++){
scanf("%d%d%d", &a, &b, &c);
vec[a].push_back(mp(c, b));
vec[b].push_back(mp(c, a));
}
printf("%d\n",Prim(a));
return 0;
}
| cs |
<Kruskal Algorithm>
//Kruskal algorithm
#include <cstdio>
#include <algorithm>
using namespace std;
struct T{
int s, e, v;
bool operator<(const T other)const{
return v < other.v;
}
}ver[100001];
int V, E;
int g[10001];
int find(int x){
if (x == g[x]) return x;
return find(g[x]);
}
void merge(int u, int v){
u = find(u);
v = find(v);
if (u == v) return;
if (u > v){
int tmp = u;
u = v;
v = tmp;
}
g[u] = v;
}
int main(){
int ans = 0;
scanf("%d%d", &V, &E);
for (int n = 0; n < E; n++)
scanf("%d%d%d", &ver[n].s, &ver[n].e, &ver[n].v);
for (int n = 0; n <= V; n++) g[n] = n;
sort(ver, ver + E);
//algorithm start
int cnt = 0;
for (int n = 0; cnt < V - 1; n++){
int a = find(ver[n].s), b = find(ver[n].e);
if (a != b){
merge(a, b);
ans += ver[n].v;
cnt++;
}
}
printf("%d\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기