[백준] 2316 도시 왕복하기 2 + 정점분할 기법,모델링

문제

N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방문했던 도시(1, 2번 도시 제외)를 두 번 이상 방문하지 않으려 한다. 한 번 1번 도시와 2번 도시 사이를 오갈 때, 반드시 한 개 이상의 도시를 중간에 거쳐야 한다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다.

입력

첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 서로 다른 두 도시의 번호가 주어진다.

출력

 

첫째 줄에 왔다 갔다 할 수 있는 최대 횟수를 출력한다.

 

네트워크 플로우 문제는 모델링이 중요하단걸 깨달은 문제....

1번도시와 2번 도시를 오가려 하는데, 한번 방문했던 도시는 두번다시 방문해선 안됩니다.

그래서 만약 방문여부를 표시한 배열로 문제를 풀면 오답입니다.

왜냐하면 이상한 길로 탐색을 성공했더라도 이후의 탐색이 불가능하기 때문입니다.

쥬황색 길을 탐색했지만 오답입니다.

 따라서,,, 에드먼드카프알고리즘으로 흘릴텐데 어떤식으로 흘릴거냐면 하나의 정점을 둘로 쪼개서, 들어오는 정점과 나가는 정점을 나눠줄겁니다.

 

 

이렇게 한 정점을 들어오는 정점과 나가는 정점으로 나누게 된다면

역방향 간선으로는 음의 유량이 흐른다는 점을 이용해 상쇄시킬 수 있습니다!!

따라서 2가지 방법을 모두 찾을 수 있습니다. 

모델링이 어렵습니다....

 

한 정점 내에서 in->out 정점의 capacity는 1이고,

두 정점 간 out->in 정점의 capacity는 INF입니다.

 

이렇게 해주면 한 정점내에서 두번 플로우가 흐르는걸 방지할 수 있습니다.(방문처리가능)

한번 루트를 찾았을때 흐르는 유량은 1이므로,, 굳이 얼마나 흐르는지 확인할 필요는 없습니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };

using namespace std;
int N, P, a, b, c[804][804], f[804][804], INF = 987654321, ans;
vi adj[804];
//n-in : 1~400
//n-out : 401~800

int main() {
	FAST;
	cin >> N >> P;
	while (P--) {
		cin >> a >> b;
		//a-out >> b-in
		//b-out >> a-in
		adj[a + N].push_back(b);
		adj[b].push_back(a + N);
		adj[b + N].push_back(a);
		adj[a].push_back(b + N);

		c[a + N][b] = INF;
		c[b + N][a] = INF;

	}
	for (int i = 1; i <= N; i++) {
		adj[i].push_back(i + N);
		adj[i + N].push_back(i);
		c[i][i + N] = 1;
	}

	while (1) {
		queue<int>q;
		q.push(N+1);
		int p[802];
		fill(p, p + N * 2 + 1, -1);
		p[N + 1] = 1;
		while (!q.empty()) {
			auto cur = q.front();
			q.pop();
			for (auto nxt : adj[cur]) {
				if (p[nxt] == -1 && c[cur][nxt] - f[cur][nxt] > 0) {
					p[nxt] = cur;
					q.push(nxt);
				}
			}
		}
		if (p[2] == -1)break;
		ans++;
		for (int i = 2; i != 1; i = p[i]) {
			f[p[i]][i] += 1;
			f[i][p[i]] -= 1;
		}
	}
	cout << ans;
}