15741번 - 일반 그래프 최대 가중치 매칭

문제

N개의 정점과 M개의 무방향 간선으로 이루어진 가중치 그래프가 입력으로 주어질 때에, 해당 그래프에서 최대 가중치 매칭의 가중치 합을 출력하는 프로그램을 작성하시오.

그래프 G = (V, E)(|V|=N, |E|=M)에서 매칭 T는 E의 부분 집합이며, T의 어떠한 두 원소가 같은 정점을 공유해서는 안 된다.

최대 가중치 매칭이란 그러한 매칭 중 가중치의 합이 최대인 것을 이르는 말이다.

입력

첫째 줄에 정점의 수를 나타내는 N(1 ≤ N ≤ 400)과 간선의 개수를 나타내는 M(1 ≤ M ≤ N(N-1)/2)이 주어진다.

둘째 줄부터 M개의 줄에 걸쳐서 각 간선의 정보가 주어진다. 간선의 정보는 해당 간선을 이루는 서로 다른 두 정점의 번호와 가중치로 구성되어져 있다.

정점의 번호는 1 이상 N 이하의 자연수이고, 간선의 가중치는 1 이상 5억 이하의 자연수이다. 두 정점 사이에 간선은 최대 1개이다.

출력

첫째 줄에 최대 가중치 매칭의 가중치 합을 출력한다.

제한

힌트