글 읽기 - 어디서 시간초과가 나는 걸까요?

playsworld16 3년 전 0

전형적인 MCMF 문제인데

어디선가 무한 루프라도 걸리는 걸까요?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 100000000

ll c[802][802];  // 직원 1 ~ 400, 일 401 ~ 800, source: 0, sink: 801
ll f[802][802];
ll cost[802][802];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll n, m;
	cin >> n >> m;

	vector<vector<ll>> adj(802);

	for (int i = 1; i <= n; i++) {
		ll x;
		cin >> x;
		while (x--) {
			int a, b;
			cin >> a >> b;

			adj[i].push_back(a + 400);
			adj[a + 400].push_back(i);
			c[i][a + 400] = 1;
			cost[i][a + 400] = b;
			cost[a + 400][i] = -b;
		}
	}

	// source - 직원
	for (int i = 1; i <= n; i++) {
		adj[0].push_back(i);
        adj[i].push_back(0);
		c[0][i] = 1;
	}

	// 일 - sink
	for (int i = 1; i <= m; i++) {
		adj[i + 400].push_back(801);
		c[i + 400][801] = 1;
	}

	ll cnt = 0, ans = 0;
	while (1) {

		vector<ll> dist(802, INF), from(802, -1);
		dist[0] = 0, from[0] = 0;

		vector<bool> inQ(802);
		inQ[0] = 1;
		queue<int> q;
		q.push(0);
		while (!q.empty()) {

			ll a = q.front();
			q.pop();
			inQ[a] = 0;

			if (a == 801) break;

			for (ll i : adj[a]) {
				if (dist[i] > dist[a] + cost[a][i] && c[a][i] - f[a][i] > 0) {

					dist[i] = dist[a] + cost[a][i];
					from[i] = a;

					if (!inQ[i]) {
						
						inQ[i] = 1;
						q.push(i);
					}
				}
			}
		}
		if (from[801] == -1) break;

		ll td = INF;
		ll x = 801;
		while (x != 0) {
			td = min(td, c[from[x]][x] - f[from[x]][x]);
			x = from[x];
		}

		x = 801;
		while (x != 0) {
			f[from[x]][x] += td;
			f[x][from[x]] -= td;
			ans += cost[from[x]][x] * td;
			x = from[x];
		}

		cnt++;
	}
	cout << cnt << '\n' << ans << '\n';

}

byeongkeunahn 3년 전 2

63번 줄처럼 종결조건을 주게 되면, 소스에서 싱크로 가는 경로로 찾은 것이 최단경로가 아닐 수 있습니다. 그러면 다음과 같은 경우에 음수 사이클이 생길 수 있습니다.

소스를 s, 싱크를 t라 합시다. u, v는 중간의 어떤 정점입니다.
- s ~> u ~> t의 cost는 5입니다.
- s ~> v ~> t의 cost는 3입니다.
그런데, s ~> u ~> t가 먼저 발견되었다고 합시다. 그러면 더 좋은 경로인 s ~> v ~> t는 발견되지 않습니다.
- flow augmentation을 하면서, s ~> v ~> t ~> u ~> s의 음수 사이클이 생깁니다. (3-5 = -2)

음수 사이클이 뭐가 문제인가 하면, 바로 다음 iteration에 SPFA를 시행할 때, 무한 루프에 빠지게 되어 문제입니다. 이 상황은 애초에 최적의 비용을 갖는 경로를 택하지 않은 잘못에서 기인하며, 사후적으로 되돌릴 수 없습니다. 음수 사이클이 생긴 이상 s -> t로 가는 최단경로라는 것이 존재하지 않기 때문이죠.

MCMF는 반드시 매회 최적의 flow augmentation 경로를 찾아야 제대로 돌아갑니다.

playsworld16 3년 전 0

최단경로는 다익스트라로만 처리하다보니 이런 실수를 했네요..

정말 감사합니다!

댓글을 작성하려면 로그인해야 합니다.