시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

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개이다.

출력

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

예제 입력 1

3 3
1 3 10
1 2 3
2 3 5

예제 출력 1

10

예제 입력 2

7 20
5 7 9
3 7 4
3 6 6
2 5 8
5 1 9
1 3 6
6 5 1
2 7 4
2 3 5
6 4 2
7 1 5
5 4 4
4 1 3
5 3 9
7 6 4
2 1 3
4 3 9
6 2 7
4 2 8
6 1 10

예제 출력 2

28

출처

  • 문제를 만든 사람: appa