rofn123

import java.util.Scanner; //union find을 이용하면, 특정한 부분집합에 지불할 돈의 최솟값을 구할 수 있으며, //특정한 부분집합들의 최소값을 합친 것이 모든 친구들을 사귈수 있는 돈의 최솟값이 된다!!!!! //특정한 부분집합의 지불할 돈의 최솟값을 구하기 위해서는 그냥, 각각의 사람들의 대표노드를 구하고, 그 대표 사람을 사기(?)위한 돈의 최솟값을 구하면 된다. class Main { static int find(int p[], int x) {//노드가 속한 부분집합의 대표노드 구하기 if(p[x] == x) return x; return p[x] = find(p, p[x]); } static void merge(int p[], int x, int y) {//두개의 노드..

#include #define M 1000000000 //union find을 이용하면, 특정한 부분집합에 지불할 돈의 최솟값을 구할 수 있으며, //특정한 부분집합들의 최소값을 합친 것이 모든 친구들을 사귈수 있는 돈의 최솟값이 된다!!!!! //특정한 부분집합의 지불할 돈의 최솟값을 구하기 위해서는 그냥, 각각의 사람들의 대표노드를 구하고, 그 대표 사람을 사기(?)위한 돈의 최솟값을 구하면 된다. int find(int p[], int x) { //노드가 속한 부분집합의 대표노드 구하기 if(p[x] == x) return x; return p[x] = find(p, p[x]); } void merge(int p[], int x, int y) { //두개의 노드의 부분집합을 합치기 x = find(..

#include #include int find(int p[], int x) { //노드가 속한 부분집합의 대표 노드를 찾는 함수 if(p[x] == x) return x; return p[x] = find(p, p[x]); } void merge(int p[], int x, int y) {//두개의 노드의 부분집합을 합치는 함수 x = find(p, x); y = find(p, y); if(x!=y) p[x] = y; //p[y] = x 도 상관없습니다. return; } int same(int p[], int x, int y) { //두개의 노드가 같은 부분집합인지를 찾는 함수 x = find(p, x); y = find(p, y); return x==y; } int main(void) { int n..

#include #include int find(int parent[], int x) { if(parent[x] == x) return x; return parent[x] = find(parent, parent[x]); } void merge(int parent[], int x, int y) { x = find(parent, x); y = find(parent, y); if(x != y) parent[x] = y; return; } int same(int parent[], int x, int y) { x = find(parent, x); y = find(parent, y); return x == y; } int main(void) { int n, m; scanf("%d", &n); scanf("%d", ..

#include #define INF 100000000 int main(void) { int n, m; scanf("%d %d", &n, &m); int d[n][n]; for(int i=0; i

#include #define INF 100000000 int main(void) { int n, m, r; //입력 scanf("%d %d %d", &n, &m, &r); int d[n][n]; //최단 거리를 담는 배열 int bag[n]; //각 구역에서 얻는 물건들 개수 for(int i=0; i

#include #define INF 100000000 int main(void) { int n, m, t; //input scanf("%d %d %d", &n, &m, &t); int d[n][n]; //최단거리 배열 for(int i = 0; i2 : 8cm 1->2 와 1->3->2에서 12 > 4, 12 > 8이며, 4, 8중 더 큰 것은 8이다. 고로 1->2는 8로 바뀐다. 이를 Floyd Warshall에서 돌리면 된다. https://www.acmicpc.net/problem/23286 23286번: 허들 넘기 첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 ..

#include #define INF 100000000 int main(void) { int n; scanf("%d", &n); int d[52][52] = {0}; //최단 연결 배열 for(int i=0; i

#include #define INF 10000000 int main(void) { //단방향 그래프 int n, m; scanf("%d %d", &n, &m); int d[501][501]; //최단거리를 담는 배열 for(int i = 1; i