크루스칼 알고리즘 썸네일형 리스트형 BOJ)4386 Freckles 문제: icpc.me/4386 N개의 점들이 주어지고 각 점들사이의 가중치는 거리와 비례한다 할 때 MST를 구성하는 문제다. N이 100밖에 되지 않으니 N^2의 방법으로 간선들을 구해준 후 크루스칼을 돌려주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std;int n, par[101], it;double r;pair p[101];priority_queue pq;double calc(pair cx, pair cy) { return sqrt((cx.first - cy.first)*(cx.first - cy.first) + (cx.se.. 더보기 BOJ)4343 Arctic Network 문제: icpc.me/4343 P개의 전초기지가 있을 때 S개의 전초기지는 위성채널과 연결되어 있을 때 전초기지 전체가 위성채널과 연결되게 하는데 필요한 마지막 최소 연결비용을 출력하는것이다. 연결비용은 두 전초기지의 거리와 같다. 우리는 P-S개의 간선을 연결하는 MST를 구현하여 마지막으로 연결되는 간선의 가중치를 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include #include using namespace std;int t, n, m, x, y, par[501], c;pair p[501];double r;double calc(pa.. 더보기 BOJ)1647 도시 분할 계획 문제: icpc.me/1647 최소 스패닝 트리를 구해주면 된다. 주의할 점은 하나인 마을을 두개로 나누고 싶다고 하고 있기 때문에 N-2개의 간선만 연결해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std;vector vt;int n, m, a, b, c, r;int par[100010];int find(int x) { if (par[x] == x)return x; return par[x] = find(par[x]);}void merge(int x, int y,int z) { x = find(x); y = find(y); if (x ==.. 더보기 이전 1 다음