글 읽기 - MCMF 시간초과 이유를 모르겠습니다.

simm4256 4년 전 0

spfa로 최단경로 찾아서 유량 흘리는 전형적인 mcmf를 돌렸는데 TLE 해결을 못하겠습니다..

그래프 모델링은

0 : sourse

1 : 방 A, 2 : 방 B

3~n+2 : 각 팀

n+3 : sink

로 했습니다.

/*
풍선
https://www.acmicpc.net/problem/4716
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <memory.h>
#define END (2 + n + 1)
#define maxN 1008
#define INF 987654321
using namespace std;
typedef long long ll;

int n, x, y, a, b, c, cap[maxN][maxN], flow[maxN][maxN], cost[maxN][maxN], parent[maxN], ans;
vector<int> edge[maxN];

bool spfa() {
	int dist[maxN], isInQ[maxN], cnt[maxN];
	memset(parent, -1, sizeof(parent));
	memset(isInQ, 0, sizeof(isInQ));
	memset(cnt, 0, sizeof(cnt));
	fill(dist, dist + maxN, INF);
	queue<int> q;
	q.push(0); isInQ[0] = 1; dist[0] = 0; cnt[0] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop(); isInQ[now] = 0;
		for (auto to : edge[now]) {
			if (cap[now][to] <= flow[now][to] || dist[to] <= dist[now] + cost[now][to])
				continue;
			dist[to] = dist[now] + cost[now][to];
			parent[to] = now;
			if (!isInQ[to]) {
				if (++cnt[to] > 3 + n) {
					cout << "ERROR";
					exit(0);
				}
				q.push(to); isInQ[to] = 1;
			}
		}
	}
	return parent[END] != -1;
}

void flowing() {
	int minFlow = INF, i, child[maxN];
	for (i = END; i != 0; i = parent[i]) {
		int p = parent[i];
		child[p] = i;
		minFlow = min(minFlow, cap[p][i] - flow[p][i]);
	}
	for (i = END; i != 0; i = parent[i]) {
		int p = parent[i];
		flow[p][i] += minFlow;
		flow[i][p] -= minFlow;
	}
	ans += minFlow * cost[child[0]][child[child[0]]];
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	while (1) {
		int i, j;
		for (i = 0; i < maxN; i++) {
			edge[i].clear();
		}
		memset(cap, 0, sizeof(cap));
		memset(flow, 0, sizeof(flow));
		memset(cost, 0, sizeof(cost));
		ans = 0;
		cin >> n >> x >> y;
		if (!n) return 0;
		// 0 : Source, 1 : A방, 2 : B방
		cap[0][1] = x; cap[0][2] = y;
		edge[0].push_back(1); edge[0].push_back(2);
		edge[1].push_back(0); edge[2].push_back(0);
		for (i = 1; i <= n; i++) {
			cin >> a >> b >> c;
			cap[1][2 + i] = max(cap[0][1], a); cap[2][2 + i] = max(cap[0][2], a);
			edge[1].push_back(2 + i); edge[2].push_back(2 + i);
			edge[2 + i].push_back(1); edge[2 + i].push_back(2);
			cost[1][2 + i] = b; cost[2 + i][1] = -b;
			cost[2][2 + i] = c; cost[2 + i][2] = -c;
			edge[2 + i].push_back(END); edge[END].push_back(2 + i);
			cap[2 + i][END] = a;
		}
		
		while (spfa()) {
			flowing();
		}
		cout << ans << '\n';
	}
}

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

문제

문제

출처

ICPC

MCMF 시간초과 이유를 모르겠습니다.

simm4256 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말