네트워크 플로우 유형 정리

중요하게 다뤄지는 테마로는

Min-Cut Max-Flow Theorem문제부터 이분매칭, 그리고 MCMF까지있다.

3가지를 모두 깊게 파지는 못했지만 그래도 풀면서 알게된 테크닉들을 적어보려한다.

문제들은 모두 백준에있는 문제들로 했으며, 전역하면 코드포스나 탑코더에 있는 문제들도 풀어보려한다.

 

알고리즘 하나를 알게되면 관련된 문제들을 모두 풀어보려고 노력한다.

따라서 유형을 정리한다고 하면

백준에있는 알고리즘 분류를 통해 알게되는 문제들을 정리한다는 말이다.

정리가 오늘 하루만 하는것도아니고.. 계속해서 업데이트되는 글이 될것이다.

 

SRC = 시작점, SINK = 도착점입니다.

 

[Min-Cut Max-Flow Theorem]

최대 플로우가 최소컷이라는 재미있는 이론이다.

이걸 처음 접할 때만해도 컷이라는걸 추상적으로만 이해해서, 문제에 적용하거나 다른 이론들을 이해하는데 써먹지 못했다. 

컷은 말그대로 자르는건데, 플로우 그래프의 간선들을 자를수도, 정점들을 자를수도 있다.

아름답게 직선으로 잘라지지 않는다. 그래서 상상으로 아! 이런건가? 하고 감을 잡고, 여러 예제를 돌려보며 확실히 이해하고있다.

• 플로우 그래프의 간선들을 자르는 유형.

https://www.acmicpc.net/problem/13161

13161번: 분단의 슬픔

1. 그래프 모델링

 

진영이 A와 B 두개로 나뉘어 있다.

무조건 A에 속해야하는 사람, B에 속해야하는 사람들을 진영으로 보고,

둘 중 하나를 SRC와 이어주고 나머지를 SINK와 이어준다.

이제 컷을 중점으로 생각해보자.

슬픔의 합이 최소가 된다는건 사람과 사람을 잇는 간선의 용량을 슬픔의 정도로 하고,

플로우를 흘려주면서 포화상태가 되는 간선이 컷에 해당된다고 예상할 수 있다.

그럼 SRC, SINK와 이어진 간선들의 용량은 어떻게 해줘야할까?

만약 슬픔의 정도보다 작다면 어떻게 될까?

그러면 컷이 시작점 또는 도착점과 이어질 수도 있는데, 시작점 또는 도착점과 사람을 잇는 슬픔의 정도는 당연히 없다.

컷으로 만들어봤자 의미가 없는 컷이된다.

그러면 사람과 사람사이의 간선을 중점으로 돌리려면 어떻게해야할까?

SRC와 SINK와 이어지는 간선들은 용량을 무한대로 주면 된다.

 

2. 플로우 흘리기

플로우를 흘려주면 포화된 간선들이 있을것이다. 이게 컷이될텐데, 이제 누가 어느진영에 속하는지 어떻게 알 수 있을까?

컷이라고 하면 포화된 간선들을 의미할거고, SRC에 해당하는 진영에서 SINK에 해당하는 진영으로 못가는 경계선이 될것이다. 따라서 SRC에서 도달가능한 정점들은 모두 SRC진영에 해당하는 정점들이 된다.

 

3. 태클

그럼 모두 A진영이거나 B진영인 경우는 어떻게 해야할까?

의미없다, 아무도 슬퍼하지 않기 때문이다.

 

4. 정리

컷에 해당하는것은 포화된 간선을찾는것과 같다는 점.

컷을하면 두개의 집합으로 나뉘고, 이는 SRC에서 도달가능한 정점들을 찾음으로써 집합을 구체적으로 알 수 있다는 점.

용량을 무한대로 주는 아이디어.

 

5. 어?

에드몬드-카프면 TLE가 난다고 슬쩍(?)봐서 디닉으로 돌렸는데, 왜 시간초과야;;

사실 디닉을 제대로 구현해본적이 없었다. 개념만 알고 아슬아슬하게 답을 맞춘경우만 있었다.

왜 틀렸는지 보니까, 디닉을 구현할 때 쓰이는 dfs부분이 비효율적이었다.

[ 처음 쓰인 dfs 코드 ]

int dfs(int now, int end, int flow){
	if(now == end) return flow;
	for(int next : adj[now]){
		int remain = c[now][next]-f[now][next];
		if(level[next] == level[now] + 1 && remain > 0){
			int diff = dfs(next, end, min(flow, remain));
			if(diff > 0){
				f[now][next] += diff;
				f[next][now] -= diff;
				return diff;
			}
		}
	}
	return 0;
}

이 코드로 dfs를 돌리면 어떤 정점을 탐색할 때마다 그 정점에 붙어있는 간선들을 다시 첨부터 마지막까지 탐색하게 된다. 

 

[ 나중에 쓰인 dfs 코드 ]

int dfs(int now, int end, int flow){
	if(now == end) return flow;
	int s = adj[now].size();
	for(int &i = work[now]; i<s; i++){
		int next = adj[now][i];
		int remain = c[now][next]-f[now][next];
		if(level[next] == level[now] + 1 && remain > 0){
			int diff = dfs(next, end, min(flow, remain));
			if(diff > 0){
				f[now][next] += diff;
				f[next][now] -= diff;
				return diff;
			}
		}
	}
	return 0;
}

하지만 이 코드는 한번 정점을 탐색할 때마다 다음에 몇번째 간선부터 보면 되는지를 알려줌으로써 시간복잡도를 무지막지하게 줄일 수 있다. 

 

• 플로우 그래프의 정점들을 자르는 유형.

사실 정점을 자르지 않는다.

다만 문제에서 정점을 한번만 지난다거나, 각 정점에 뭔가 가중치를 넣는 경우가 있다.

이럴때는 정점분할(다들 이렇게 부르더라)을 해줘야한다.

https://www.acmicpc.net/problem/1420

1420번: 학교 가지마!

이 문제는 SRC와 SINK가 명시되어있어서 어디를 SRC와 연결하고, 어디를 SINK와 연결하는지 생각을 덜해도 되지만, 장애물을 칸에 놓아야한다는게 마음에 걸린다.

어떤칸에서 그 옆의 칸으로 간선을 이어준다는건 알겠는데.. 장애물을 그 칸에 놓아야한다는건 어떻게 만들어야할까??

 

정점분할은 각 정점을 두개로 나누는것을 말한다.

나눠진 정점 중 하나는 다른 정점에서 들어오는 간선이 붙고, 다른 하나는 다른 정점으로 나가는 간선이 붙을것이다.

또한 나눠진 두 정점을 한개의 간선으로 이어주는데, 이 간선에 용량을 주어진 가중치나 1로 둠으로써 문제를 해결하게 하는게 바로 정점분할이다.

정점을 나눈다는건 또한 무향그래프로 주어졌을 때, 이를 단방향으로 바꿔줄 수도 있다.

1번정점과 2번정점이 있고, 둘이 양방향 간선으로 이어져있다고 하자. 근데 각 정점을 정점분할 해보자.

다른정점으로부터 1번정점으로 들어오는 간선은 [1]정점에, 1번정점에서 다른 정점으로 나가는 간선이 붙는 정점은

[1'] 정점이라고 하자. 2번도 마찬가지로 쪼개놓고 서로를 이어주면, [1'] --> [2], [2'] --> [1] 이렇게 이어줌으로써 양방향이었던 간선을 두개의 단방향 간선으로 만들어준다. 또한 어떻게 들어오던 [N] --> [N']으로 각 정점 내부에서도 무조건 같은 방향으로만 플로우가 흘러, 문제를 생각할 때도 수월해진다.

난 정점을 분할할 때, 모든 정점의 개수가 V라고 하자면 N번 정점은 N과 N+V번으로 인덱스를 줘서 푼다.

물론 이렇게 안하고 다른방법으로 하는 분들도 많이 봤다.

 

1. 그래프 모델링

이제 장애물을 어떻게 정점에 놓는지 알았으니 그래프를 모델링해보자.

이제 컷을 하게되는 부분은 각 정점내부에 있는 간선(1번이라면 [1]과 [1']사이에 있는 하나의 간선)들이다.

따라서 이 용량을 1로 둔다. 즉 정점은 딱 한번씩만 지날 수 있는거다.

정점들 서로서로를 이어주는 간선의 용량은 어떻게 해줘야할까? 정점 내부에 있는 간선의 용량을 1로 줬다는 말은 정점을 단 한번만 지날 수 있다는 말이다. 즉, 정점들 서로서로를 이어주는 간선들의 용량도 1로두어도 상관이 없다.

정점 하나를 딱 한번만 거칠 수 있는데, 간선의 용량을 크게줘봐야 의미가 없다는 말이다.

 

2. 플로우 흘리기

따라서 장애물을 제외한 모든 칸들을 상하좌우로 묶어주고 플로우를 흘려주자.

최대로 흐른 플로우가 의미하는것을 학교로 갈 수 있는 경로 중 막아야하는 최소 장애물을 수와 같아진다.

 

3. 태클

그렇게 만들면 한번 플로우가 흐른자리는 모든 정점이 막히니까, 플로우가 덜 흐르는거 아닌가?

 

K	.	.	.	.
.	.	.	#	#
#	.	.	.	.
.	.	.	.	H

위와같은 예시에서 다음과 같이 플로우가 흘렀다고 가정해보자.

K	.	.	.	.
플	플	플	#	#
#	.	플	플	플
.	.	.	.	H

한번 흐를 때 이렇게 흐르면 플로우가 한번밖에 못흐르는거 아닌가?

아쉽게도 우리가 쓰는 알고리즘은 항상 더 많은 플로우를 흘리기 위해 설계되어있다.

저렇게 흘렀었더라도, 역방향간선을 적절히 사용해서 더 많은 플로우를 흘렸을 것이다.

 

4. 정리

정점을 단 한번만 지나도록 하는 아이디어.

이를 통해 정점 자체를 컷으로 만드는 방법.

 

5. 어?

뭐야.. 왜 한번만 흐르는거지?

사실 이 문제를 많이 틀렸었는데, 정점을 분할해놨기 때문이었다.

시작점 K에서 분할된 두 정점중 어느것을 SRC로 도착점인 H에서 도 마찬가지 이유로 헤멨었다.

K에서는 나가는 정점 H에서는 들어오는 정점을 SRC와 SINK로 만들어야한다. 안 그러면 단 한 번만 흐르기 때문이다.

또한 이와 같은 맥락에서 -1이 되는경우도 헤메다보면 3번정도 더 틀릴 수 있다.