[백준] 3640 제독

문제

미힐 더 라위터르는 네델란드의 역사에서 가장 유명한 제독이다. 그는 17세기에 벌어진 영국-네델란드 전쟁에서 전공을 세웠다.

라위터르가 살던 시절에 그래프 이론이 연구되기 시작했고, 제독은 이론을 해전 계획에 자주 이용했다. 바다 위의 중간 지점은 정점으로 나타낼 수 있고, 각 중간 지점에서 이동할 수 있는 뱃길은 방향성이 있는 간선으로 나타나 있다. 두 중간 지점 W1와 W2사이에 뱃길 W1 → W2는 최대 한 개 있을 수 있다. 각 간선의 가중치는 그 뱃길을 안전하게 이동하기 위해 발사해야 하는 포탄의 수이다. 

라위터르의 가장 유명한 전술은 "De Ruyter Manoeuvre"이다. 이 전술은 한 중간 지점에서 두 전함이 서로 다른 방향으로 출발을 한다. 그 다음 적함과 전투를 하면서 이동한 다음 목적지에서 다시 만나는 전술이다. 이 전술에서 두 전함은 항상 겹치지 않는 뱃길을 택해야 하며, 출발과 목적지를 제외하고 같은 중간 지점이나 같은 뱃길을 지나면 안 된다.

라위터르는 돈을 낭비하는 것을 좋아하지 않는다. 따라서, 포탄을 가장 적게 발사하는 뱃길을 택하려고 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 입력의 끝은 EOF로 확인할 수 있다.

테스트 케이스의 첫째 줄에는 중간 지점의 수 v와 뱃길의 수 e가 주어진다. (3 ≤ v ≤ 1000, 3 ≤ e ≤ 10000) 다음 e개 줄에는 뱃길의 정보 ai, bi, ci가 주어진다. (1 ≤ ai, bi ≤ v, ai ≠ bi, 1 ≤ ci ≤ 100) ai는 뱃길의 시작 지점, bi는 도착 지점, ci는 그 뱃길로 이동할 때 발사해야 하는 포탄의 수이다.

전술의 시작 지점은 1이고, 목적지는 v이다. 항상 1과 v사이에 겹치지 않는 경로가 적어도 두 개 있다.

출력

각 테스트 케이스에 대해서, 두 전함이 전술을 따르면서 발사해야 하는 포탄의 최소 개수를 출력한다.

 

한번 방문한 정점과 간선은 재방문 하지 않으면서,

1번부터 v번 노드까지 가는데 최소비용을 2번 구해야 합니다.

MCMF문제입니다. SPFA를 사용합니다.

이때 이미 방문한 간선은 재방문해선 안되므로, 정점을 분할하여 모델링하면 됩니다.

한번 흘릴때 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 v, e, x, y, z, c[2002][2002], f[2002][2002], INF = 987654321, ans;
vi adj[2002];
int cost[2002][2002];
//출발 in:1 out:1+v
//도착 in:v out:v+v=2v

int main() {
	FAST;
	while (cin >> v >> e) {
		ans = 0;
		mset(c);
		mset(f);
		mset(cost);
		REP(i, 2 * v + 2)adj[i].clear();
		while (e--) {
			cin >> x >> y >> z;
			//a에서 b, 비용은 c
			//a in 에서는 b out으로 -c 비용으로 갈 수있음
			adj[x + v].push_back(y);
			adj[y].push_back(x + v);

			adj[y + v].push_back(x);
			adj[x].push_back(y + v);

			cost[x+v][y] = z;
			cost[y][x + v] = -z;

			c[x + v][y] = 1;
		}
		REP(i, v) {
			adj[i].push_back(i + v);
			adj[i + v].push_back(i);
			c[i][i + v] = 1;
		}

		rep(rp, 2) {
			queue<int>q;
			q.push(1 + v);
			int p[2002], dist[2002], inQ[2002];
			fill(dist, dist + 2002, INF);
			fill(p, p + 2002, -1);
			mset(inQ);
			p[1 + v] = 1;
			inQ[1 + v] = 1;
			dist[1 + v] = 0;
			while (!q.empty()) {
				auto cur = q.front();
				inQ[cur] = 0;
				q.pop();
				for (auto nxt : adj[cur]) {
					if (c[cur][nxt] - f[cur][nxt] > 0 && dist[nxt] > dist[cur] + cost[cur][nxt]) {
						dist[nxt] = dist[cur] + cost[cur][nxt];
						p[nxt] = cur;
						if (!inQ[nxt]) {
							q.push(nxt);
							inQ[nxt] = 1;
						}
					}
				}
			}
			for (int i = v; i != 1; i = p[i]) {
				f[p[i]][i] += 1;
				f[i][p[i]] -= 1;
				ans += cost[p[i]][i];
			}
		}
		cout << ans << "\n";
	}
	
}