본문 바로가기

전체 글

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)13325 이진 트리 문제: icpc.me/13325 포화 이진트리의 높이 K가 주어 질 때 에지의 가중치를 증가시켜서 루트에서부터 리프까지의 거리를 모두 같게 만드는 문제이다. 아래에서 부터 부모가 같은 두노드의 엣지의 가중치 차이를 바텀업으로 중첩시켜서 증가시켜주면 된다. 12345678910111213141516171819#include #include using namespace std;int n, a[1 더보기

티스토리툴바