[백준] 9413 제주도 관광

문제

제주도는 관광객들이 많이 찾는 도시이다. 제주도에는 교차로가 N개, 일방통행 도로 M개가 있다. 각각의 도로는 한 교차로와 다른 교차로를 연결한다. 한 교차로 쌍을 연결하는 도로의 개수가 여러 개일 수 있다.

사실 제주도의 도로는 매우 신기한 형태로 건설되었다. 한 교차로에서 도로를 따라 돌아다니다가 시작한 교차로로 돌아오는 일은 불가능하다. (그럼 제주도에 사는 사람들은 어떻게 출퇴근을 하는 것일까?)

두 그룹이 제주도를 여행할 계획을 세우고 있다. 각 그룹은 한 교차로에서 여행을 시작해 도로를 따라 다니면서 여행을 할 것이다. 하지만, 두 그룹은 사이가 매우 좋지 않기 때문에, 같은 교차로를 공유하면 안 된다. 즉, 두 경로 P1, P2를 구해야 하는데, 각각의 Pi (1 ≤ i ≤ 2)는 한 교차로 si에서 시작해서 ti에서 여행을 마쳐야 하고, 중간에 공유하는 교차로가 있으면 안 된다. 경로의 시작점과 도착점도 겹치면 안 된다. 하지만, Pi가 교차로를 하나만 포함하는 경우는 가능하다. (si = ti)

두 계획을 세우는데, 두 경로에 포함된 교차로 수의 합을 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다.

각 테스트 케이스의 첫째 줄에는 교차로의 수 N과 도로의 수 M이 주어진다. (1 ≤ N ≤ 300, 1 ≤ M ≤ 3000) 교차로는 1번부터 N번까지 번호가 매겨져 있다. 다음 M개의 줄에는 도로의 정보를 나타내는 A와 B가 주어지며, A에서 B로 향하는 일방통행 도로라는 뜻이다.

 

출력

각 테스트 케이스마다, 문제의 조건을 만족하면서, 두 경로에 포함된 교차로의 최대 개수를 한 줄에 하나씩 출력한다.

 

 

두 경로를 찾아야하는데, 같은 정점을 통과해서는 안됩니다.

따라서 정점을 분할하는 flow문제가 됩니다.

이때, 두 경로를 통해 가장 많은 정점을 거쳐야 하므로, 정점내에서 V in-V out 비용을 -1로 설정하고,

MCMF문제입니다.

 

소스에서 SPFA를 두번수행하면 됩니다.

#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 }, INF = 987654321;

using namespace std;

int TC, N, M, A, B, c[604][604], f[604][604], cost[604][604], ans = 0, S = 601, E = 602;
vi adj[604];
//정점분할 in : 1~V, out:1+N ~ V+N
//S=601,E=602
int MCMF() {
	int ret = 0;
	rep(i, 2) { 
		queue<int>q;
		int p[604], inQ[604], dist[604];
		fill(p, p + 604, -1);
		fill(dist, dist + 604, INF);
		mset(inQ);
		q.push(S);
		dist[S] = 0;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			inQ[cur] = 0;
			for (int nxt : adj[cur]) {
				if (dist[nxt] > dist[cur] + cost[cur][nxt] && c[cur][nxt] - f[cur][nxt] > 0) {
					dist[nxt] = dist[cur] + cost[cur][nxt];
					p[nxt] = cur;
					if (!inQ[nxt]) {
						inQ[nxt] = 1;
						q.push(nxt);
					}
				}
			}
		}
		for (int j = E; j != S; j = p[j]) {
			ret += cost[p[j]][j];
			f[p[j]][j] += 1;
			f[j][p[j]] -= 1;
		}
	}
	return ret;
}
int main() {
	FAST;
	cin >> TC;
	while (TC--) {
		cin >> N >> M;
		REP(i, 603)adj[i].clear();
		mset(c);
		mset(f);
		mset(cost);
		ans = 0;
		REP(i, N) {
			c[i][i + N] = 1;
			adj[i].push_back(i + N);

			adj[S].push_back(i);
			adj[i].push_back(S);
			c[S][i] = 1;

			adj[i + N].push_back(E);
			adj[E].push_back(i + N);
			c[i + N][E] = 1;

			cost[i][i + N] = -1;
			cost[i + N][i] = 1;
		}
		while (M--) {
			cin >> A >> B;
			c[A + N][B] = 1;
			adj[A + N].push_back(B);
			adj[B].push_back(A + N);
		}
		cout << -MCMF() << "\n";
	}
}