글 읽기 - 시간초과

jkb7676 7년 전 0

분면 예제는 잘되는데 시간초과가 나는데..

이문제는 BFS로풀면 시간초과가 나는 문제인가요?

3초라 충분할거같았는데...

#include<stdio.h>
#include<queue>
#include<memory.h>
using namespace std;

int tracer[3301];
int arr[3301][3301];
int network_flow(int source,int sink)
{
	int i;
	int flow=0;
	while(1)
	{//경로를 다시찾을때마다 queue초기화 tracer초기화 
		queue<int> q;
		memset(tracer,-1,sizeof(tracer));
		tracer[source] = source;
		q.push(source);
		while(!q.empty()&&tracer[sink]==-1)//큐가 비거나 경로를 찾으면 탈출
		{//즉 큐가 안비고 sink에 도착안했으면 계속함 
			int now = q.front();
			q.pop();
			for(i=1; i<=sink; i++)
			{
				if(arr[now][i]>=1&&tracer[i]==-1)
				{
					q.push(i);
					tracer[i] = now;
				}
			}
		}
		if(tracer[sink]==-1)break;
		int p;
		for(p = sink; p!=source; p = tracer[p])
		{
			arr[p][tracer[p]] += 1;
			arr[tracer[p]][p] -= 1;
		}
		flow += 1;
	}
	return flow;
}

int main()
{
	int i,j,n,m,k;
	int q,from;
	scanf("%d %d %d",&n,&m,&k);
	for(i=1; i<=n; i++)
	{
		scanf("%d",&q);
		for(j=1; j<=q; j++)
		{
			scanf("%d",&from);
			arr[i][from+1+n] = 1;//직원 -> 일 
		}
	}
	arr[0][n+1] = k;//source -> 추가일 
	for(i=1; i<=n; i++)arr[0][i] = 1;// source -> 직원 
	for(i=1; i<=m; i++)arr[n+1+i][n+m+2] = 1;//일 -> sink 
	for(i=1; i<=n; i++)arr[n+1][i] = k;//추가일 -> 직원 
	
	printf("%d",network_flow(0,n+m+2)); 
}

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

문제

문제

출처

ICPC

시간초과

jkb7676 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말