문제 링크 http://icpc.me/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 MST를 이용하여 풀 수 있다. 가상의 루트 노드를 하나 만들고, 어떤 물을 킬 때, 루트 노드에서 물을 끌어온다고 생각하면 쉽게 풀 수 있다. 물은 키는 행위는 루트 노드와 킬 노드를 연결시키는 것으로 매핑시키면 된다. 코드 #include using namespace std; struct T { int x, y, z; }; vector arr; int mat[302][302];..

풀이 방법 크루스칼 알고리즘을 이용하여 풀이한다. 이미 연결 된 간선은 미리 연결해놓고 가장 거리가 짧은 간선을 뽑아 사이클이 있는지 확인하고 연결한다. 코드 우선순위큐를 이용한 구현 #include #include #include #include #include using namespace std; using ll = long long; using pll = pair; using pdll = pair; pll arr[1003]; ll N, M, par[1003], cnt, lev[1003]; priority_queue pq; ll dist(pll a, pll b) { return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (..

풀이 방법 최소 신장 트리(MST)를 구하는 문제이다. MST는 prim 알고리즘과 kruskal 알고리즘을 통해 구할 수 있다. 이 풀이는 prim 알고리즘을 이용했다. cf) prim 알고리즘을 모른다면 여기를 참고하세요 코드 #include #include #include using namespace std; using pdd = pair; using pdi = pair; pdd arr[102]; bool visited[102]; priority_queue pq; // 최소 힙 int N; double ans; //점과 점 사이의 거리 double dist(pdd a, pdd b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.secon..