글 읽기 - 시간초과 도와주세요

lgioi45 7년 전 0

source - 가구작업 - 시간 - sink 순으로 그래프를 모델링하고 포드 풀커슨에서 시간초과가 나서 SPFA로 바꿨는데도 시간초과가 뜨네요

AC 받으신 분들 도움 부탁드려요

그리고 이거 정답이 여러 개일 경우 가능한 것 하나만 제출해도 되는 건가요?

예를 들어 첫 번째 테스트케이스의 경우 예제출력은

1 2 4
3 1 3 4 5 6 8
1 4 6
2 3 4 5 7

이지만

1 2 4
2 1 3 5 8
1 4 6
2 3 5 6 7

도 가능하지 않나요?

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321

int m, n;
vector<vector<int> > adj;
int cap[1001][1001], flow[1001][1001], prevv[1001], cost[1001][1001];
vector<int> upper;
int workpath[102][502];

struct Furniture{
	int s, w, d;
}fur[102];

void SPFA(int s, int t){
	upper = vector<int>(t + 1, INF);
	memset(prevv, -1, sizeof(prevv));
	vector<int> visited(t + 1, 0);
	queue<int> q;
	q.push(s);
	upper[s] = 0;
	visited[s] = 1;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		for (int i = 0; i < adj[u].size(); i++){
			int v = adj[u][i];
			if (cap[u][v] - flow[u][v] > 0 && upper[v] > upper[u] + cost[u][v]){
				upper[v] = upper[u] + cost[u][v];
				prevv[v] = u;
				if (!visited[v]) q.push(v), visited[v] = 1;
			}
		}
	}
}

int MCMF(int s, int t){
	int res = 0;
	memset(flow, 0, sizeof(flow));
	while (1){
		SPFA(s, t);
		if (upper[t] > 0) break;
		res++;
		for (int u = t; u != s; u = prevv[u]){
			flow[prevv[u]][u]++;
			flow[u][prevv[u]]--;

			if (1 <= u && u <= n && prevv[u] != s)
				workpath[u][prevv[u]] = 0;
			else if (1 <= prevv[u] && prevv[u] <= n)
				workpath[prevv[u]][u] = 1;
		}
	}
	return res;
}

int main(){
	int tc;
	scanf("%d", &tc);
	while (tc--){
		int s = 0, t = 1000;
		int mins = INF, maxd = 0, f = 0;
		scanf("%d %d", &m, &n);

		adj = vector<vector<int> >(t + 1);
		memset(cap, 0, sizeof(cap));
		memset(cost, 0, sizeof(cost));
		memset(flow, 0, sizeof(flow));
		memset(workpath, 0, sizeof(workpath));

		for (int i = 1; i <= n; i++){
			scanf("%d %d %d", &fur[i].s, &fur[i].w, &fur[i].d);
			mins = min(mins, fur[i].s);
			maxd = max(maxd, fur[i].d);
			f += fur[i].w;

			for (int j = fur[i].s; j < fur[i].d; j++){
				adj[i].push_back(j + n);
				adj[j + n].push_back(i);
				cap[i][j + n] = 1;
				cost[i][j + n] = -1;
				cost[j + n][i] = 1;
			}

			adj[s].push_back(i);
			adj[i].push_back(s);
			cap[s][i] = fur[i].w;
		}
		for (int i = mins + n; i < maxd + n; i++){
			adj[i].push_back(t);
			adj[t].push_back(i);
			cap[i][t] = m;
		}

		if (MCMF(s, t) == f){
			int cnt[102] = { 0, }, stime[101][502], etime[101][502], sflag;
			for (int i = 1; i <= n; i++){
				sflag = 0;
				for (int j = fur[i].s; j < fur[i].d; j++){
					if (workpath[i][j + n]){
						if (!sflag){
							sflag = 1;
							stime[i][cnt[i]] = j;
							if (j + 1 == fur[i].d)
								etime[i][cnt[i]] = j + 1;
							cnt[i]++;
						}
						else if (j + 1 < fur[i].d && !workpath[i][j + n + 1]){
							sflag = 0;
							etime[i][cnt[i] - 1] = j + 1;
						}
						else if (j + 1 == fur[i].d && workpath[i][j + n])
							etime[i][cnt[i] - 1] = j + 1;
					}
				}
			}

			for (int i = 1; i <= n; i++){
				printf("%d ", cnt[i]);
				for (int j = 0; j < cnt[i]; j++)
					printf("%d %d ", stime[i][j], etime[i][j]);
				printf("\n");
			}
		}
		else
			printf("0\n");
	}
	
	return 0;
}

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

문제

문제

출처

ICPC

시간초과 도와주세요

lgioi45 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말