Notice
Recent Posts
Recent Comments
Link
알고리즘 모음(C++)
백준 16398 - 행성 연결(C++) 본문
문제 링크입니다 https://www.acmicpc.net/problem/16398
간단한 MST 문제였습니다.
플로우 관리비용이 10억까지 있어, long long을 써주는 것만 주의하면 되는 문제였습니다.
Union + Find 함수를 이용해 Kruskal 알고리즘을 구현했습니다. -> 이것만 할 수 있으면 푸는 문제입니다
자세한 것은 코드를 참고해주세요!
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;
typedef struct li {
int start;
int finish;
long long int cost;
}li;
vector<li> planet;
int num;
int connect[1001];
long long int cost_min;
int planet_cost[1001][1001];
bool cmp(li a, li b) {
if (a.cost < b.cost) return true;
return false;
}
int Find(int x) {
if (connect[x] == x) return x;
else return connect[x] = Find(connect[x]);
}
void Union(int x, int y) {
int xx = Find(x);
int yy = Find(y);
connect[xx] = yy;
}
void solve() {
for (int i = 0; i <= 1000; i++) connect[i] = i;
for (int i = 0; i < planet.size(); i++) {
int x = Find(planet[i].start);
int y = Find(planet[i].finish);
if (x != y) {
Union(x, y);
cost_min += planet[i].cost;
}
}
cout << cost_min;
}
int main()
{
cin.tie(0);
cout.tie(0);
cin >> num;
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
cin >> planet_cost[i][j];
}
}
for (int i = 0; i < num; i++) {
for (int j = i + 1; j < num; j++) {
planet.push_back({ i + 1,j + 1,planet_cost[i][j] });
}
}
sort(planet.begin(), planet.end(),cmp);
solve();
return 0;
}
질문 및 조언은 댓글 남겨주세요!
'백준' 카테고리의 다른 글
백준 14621 - 나만 안되는 연애(C++) (0) | 2021.07.27 |
---|---|
백준 1774 - 우주신과의 교감(C++) (0) | 2021.07.26 |
백준 4386 - 별자리 만들기 (0) | 2021.07.24 |
백준 16202 - MST 게임 (0) | 2021.07.23 |
백준 6497 - 전력난 (0) | 2021.07.21 |