[BOJ 2316]

문제 바로가기 : https://www.acmicpc.net/problem/2316
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

BOJ 17412: 도시 왕복하기 1에서 몇 가지 옵션이 추가됐다.
중복해서 지나가지 않아야 하며, 단방향 길이 아닌 양방향 길로 연결된다는 점이다.
쓰이는 알고리즘은 같다. 하지만 알고리즘을 쓰기 전에 약간의 수정이 필요하다. 그림으로 나타내면 다음과 같다.



노드안에 또 다른 노드 2개를 설정해놓고 이 노드들 사이의 용량을 1로 설정해주면 중복해서 지나가지 않는다.
이해를 돕고자 또 다른 노드 2개를 설정한다고 했지만 사실은 원래 노드 옆에 1개를 더 추가해주는 셈이다.
IN이 원래 노드여서 인덱스가 i라면 OUT의 인덱스는 i+OUT이 된다!

a와 b가 연결됐다면 a+OUT이 b를, b+OUT이 a를 가르켜야 한다.
또 내부적으로는 a->a+OUT, b->b+OUT이 있어야 한다. 이 때 용량은 1로 설정해주자.
물론 길이라고만 했고 별도의 용량은 주어지지 않았으므로 a와 b사이 간선의 용량은 1이다.

//input
int n, p; cin >> n >> p;
for (int i = 0; i < p; i++) {
	int a, b; cin >> a >> b;
	node[a + OUT].push_back(b);
	node[b].push_back(a + OUT);

	node[b + OUT].push_back(a);
	node[a].push_back(b + OUT);

	cap[a + OUT][b] = 1;
	cap[b + OUT][a] = 1;
}

//in -> out
for (int i = 3; i <= n; i++) {
	node[i].push_back(i + OUT);
	cap[i][i + OUT] = 1;
}

주의해야할 점은, 1->2 경로 상에서 값을 구해야하기 때문에 1은 1+OUT부터 시작한다.
따라서 다음과 같이 처리해줘야 한다.

networkFlow(1+OUT, 2); //start = 1+OUT
cout << ret;