시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB145593048.387%

문제

항상 플로우 문제를 Edmond-Karp 알고리즘으로 푸는 지구이는 어느 날 정점 500개와 간선 100000개의 플로우 문제를 보게 되었다. 지구이는 열심히 플로우 그래프를 구성하고, 약 2000byte를 코딩한 후 제출했지만, 보기만 해도 기분이 좋은 초록색 글씨의 “맞았습니다!!”는 볼 수 없었다. 코드 최적화를 하다가 지친 지구이는 결국 구글갓에게 플로우 알고리즘을 물어봤고, 시간복잡도가 최악의 경우 O(V2E)인 Dinic이라는 알고리즘을 찾아냈다.

Dinic 알고리즘은 생각보다 간단했다.

  1. 유량이 남은 간선을 길이 1짜리 간선으로 생각하고 source node에서 모든 노드까지의 최단거리 dv를 구한다.
  2. dfs로 확장경로를 구해 플로우를 흘린다. 이때, 간선 u->v가 du + 1 = dv인 경우에만 플로우를 흘린다.
  3. 1, 2를 플로우가 없을 때까지 반복한다.

Dinic의 시간복잡도는 O(V2E)이며, 증명은 다음과 같다.

  1. step 1, 2는 최대 O(V)번 반복된다.
    • 이유: step 1, 2를 수행할 때 마다 dsink가 최소 1씩 증가한다. 또한, dsink는 V를 초과할 수 없다.
  2. step 1은 O(E)다.
    • 이유: BFS로 계산 가능하다.
  3. step 2는 O(VE)다.
    • 이유: 한 번 플로우를 흘릴 때마다 최소 한 개의 간선의 유량이 꽉 차기 때문에, 확장경로는 최대 O(E)번 만들어진다. 또한, 확장경로의 길이는 최대 V이다.

하지만 아직도 문제가 있었다. 지구이는 열심히 구현했음에도 불구하고 아직도 초록색 글씨를 보지 못했던 것이다. 결국 지구이는 디닉과 함께 그 문제를 포기하게 되었다.

며칠 후, 우연히 지구이의 디닉을 보게 된 도토리는 지구이에게 코드에 사소한 실수가 있었고, 그 실수 때문에 쓸모없는 연산이 많아져 시간이 오래 걸렸다는 것을 알려주었다. 하지만, 멍청한 지구이는 시간이 오래 걸리는 반례 데이터를 확인하기 전까지 그 말을 믿지 않았다.

도토리를 도와 반례 데이터를 만들어주자!

지구이의 “틀린” Dinic 코드는 여기에 있다. 지구이가 풀고 있는 문제는 1번 정점에서 N번 정점까지 플로우를 흘리는 문제이다.

지구이의 코드는 linked list로 간선을 저장했으며, list의 앞부분에 새로운 간선을 추가하기 때문에 나중에 입력된 간선을 먼저 사용함에 주의하자.

사소한 실수: 확장경로를 찾을 때, 플로우를 흘릴 수 없는 간선들은 다시 들어갈 필요가 없다. 하지만 위의 코드에서는 확장경로를 찾을 때 마다 간선을 처음부터 탐색하기 때문에 시간이 오래 걸릴 수 있다.

입력

입력은 없다

출력

첫 번째 줄에 정점 개수 N과 간선 개수 M을 출력한다. (2 ≤ N ≤ 502, 0 ≤ M ≤ N*(N-1))

두 번째 줄부터 M개의 줄에 시작 정점 s, 끝 정점 e, 최대 유량 f를 출력한다. (1 ≤ s, e ≤ N, s ≠ e, 1 ≤ f ≤ 108)

그래프에는 중복 간선이 없어야 한다.

지구이의 코드에는 간선의 참조 횟수인 cnt 변수가 있다. cnt의 값이 1억을 초과하도록 하는 데이터를 출력하여라.

출력 예시는 답이 아님에 주의하라.

예제 입력 1


						

예제 출력 1

4 5
1 2 3
1 3 4
1 4 5
2 4 2
3 4 2

출처

Contest > BOJ User Contest > 꼬마컵 > 꼬마컵 J번