이모저모

해결방법MST를 이용하면 되며 저는 크루스칼 알고리즘을 사용하였다.MST를 하기 위해서 문제의 조건을 만족하기 위해서서로 성별이 같은 대학의 edge가 들어오면 무시하고 다른 경우에만 받으면 된다.이 후 MST를 만들면 된다.시간 복잡도 O(ElogE) 아래는 소스코드이다.#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp ma..

해결방법brute force O(N!*2^N)이 된다. 무진장 크다.최소값, 최대값을 구하는 문제는 왠지 DP로 풀어야할 것 같은 느낌이 들었는데 막상 DP로 접근하려고 하니 도저히 점화식이 세워지지 않았다..... 아 너무 어렵다 생각하고 몇일 뒤에 다시 보았다.그래서 n-1개를 유심히 보면서 n개 노드 n-1개 선택.....?? 아 MST!!!!!!!!!!!!!!!!!!!!!!!가 딱 생각이 났다.MST를 이용하여 최소값을 구할수도 최대값을 구할수도 있다.MST를 만드는 알고리즘은 3가지가 있는데 거기서 나는 크루스칼 알고리즘을 사용하였다. 슈도코드1) 노드 N개 edge가 N^2가 있는 graph로 생각하고 모든 edge를 계산한다.(시청률로)2) 정렬을 수행한다.3) 유니온 파인드를 이용하여 크루..