글 읽기 - [8904, dinic] TLE인데 dinic부분의 문제일까요??

zasxer 6년 전 0

8904번 TLE가 계속 나는데, dinic부분이 문제인 걸까요??

디닉을 계속해서 이렇게 coding해왔는데.. 이번에 뭐가 틀렸을까요..ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
//0이 source end = sink
typedef struct info {	//간선 struct
	int s;			
	int e;
	int f;
	int idx;
} Info;

int N, M;
int max, flow;
Info edg[101200], tmp[101200];
int top[602], ttop[602], ttt;
//indicate backward edge
int prev[101200], back[101200];
//Dinic
int q[602], level[602];
int stack[500], tt, end;
int head, tail;

void add_edge(int s, int e, int f);
int bfs();
int dfs(int cur);

int main(void) {
	int test_case;
	int s, w, d;
	register int i, j;
	//freopen("input.txt", "r", stdin);
	scanf("%d", &test_case);
	while (test_case--) {
		//M = 가구 수, time = 1 ~ 500
		ttt = -1;
		max = flow = 0;
		scanf("%d %d", &N, &M);
		for (i = 1; i <= M; i++) {
			scanf("%d %d %d", &s, &w, &d);
			flow += w;
			max = max > d ? max : d;
			add_edge(0, i, w);
			for (j = s; j < d; j++)
				add_edge(i, M + j, 1);
		}
		end = M + max + 1;
		for (i = M + 1; i <= M + max; i++)
			add_edge(i, end, N);




		//sort edge
		ttop[0] = top[0];
		for (i = 1; i <= end; i++)
			ttop[i] = top[i] += top[i - 1];
		for (i = 0; i <= ttt; i++)
			edg[--ttop[tmp[i].s]] = tmp[i];
		///////////////////////////


		//서로 역간선을 가르킴
		for (i = 0; i <= ttt; i++) {
			if (prev[edg[i].idx]) {
				back[prev[edg[i].idx] - 1] = i;
				back[i] = prev[edg[i].idx] - 1;
			}
			else prev[edg[i].idx] = i + 1;
		}
		///////////////////////////




		//dinic구현부 -> 여기서 시간 초과가 나는 거 같음.
		while (bfs()) {
			while (dfs(0)) {
				flow--;
			}
		}
		///////////////////////////////////////////////////




		/////////////출력부////////////////////////////
		if (flow) printf("0\n");
		else {
			for (i = 1; i <= M; i++) {
				int cnt = s = 0;
				tt = -1;
				for (j = top[i] - 2; j >= top[i - 1]; j--) {
					if (!edg[j].f && !s) {
						cnt++;
						stack[++tt] = edg[j].e - M;
						s = 1;
					}
					else if (edg[j].f && s) {
						stack[++tt] = edg[j].e - M;
						s = 0;
					}
				}
				if (s) stack[++tt] = edg[j + 1].e - M + 1;
				printf("%d ", cnt);
				for (j = 0; j <= tt; j++)
					printf("%d ", stack[j]);
				printf("\n");
			}
		}
		for (i = 0; i <= ttt; i++)
			prev[i] = back[i] = 0;
		for (i = 0; i <= end; i++)
			top[i] = ttop[i] = 0;
	}
	return 0;
}

void add_edge(int s, int e, int f) {
	tmp[++ttt].s = s;
	tmp[ttt].e = e;
	tmp[ttt].f = f;
	tmp[ttt].idx = ttt >> 1;
	tmp[++ttt].s = e;
	tmp[ttt].e = s;
	tmp[ttt].f = 0;
	tmp[ttt].idx = ttt >> 1;
	top[s]++, top[e]++;
}

int bfs() {
	register int i;
	int ret = 0;
	for (i = 0; i <= end; i++)
		level[i] = 0;
	head = 0, tail = -1;
	q[++tail] = 0;
	level[0] = 1;
	int pp;
	while (head <= tail) {
		pp = q[head];
		for (i = pp ? top[pp - 1] : pp; i < top[pp]; i++) {
			if (!level[edg[i].e] && edg[i].f) {
				q[++tail] = edg[i].e;
				level[edg[i].e] = level[pp] + 1;
			}
		}
		head++;
	}
	return level[end];
}

int dfs(int cur) {
	register int i;
	if (cur == end)
		return 1;
	for (i = cur ? top[cur - 1] : cur; i < top[cur]; i++) {
		if (edg[i].f && level[cur] + 1 == level[edg[i].e]) {
			int ret = dfs(edg[i].e);
			if (ret > 0) {
				edg[i].f--;
				edg[back[i]].f++;
				return 1;
			}
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

[8904, dinic] TLE인데 dinic부분의 문제일까요??

zasxer 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말