글 읽기 - 시간초과

djghdy 5년 전 0

카프알고리즘으로 풀었고, 시간초과가 떳습니다.

근데 코드에서 한부분만 고쳐니까 아슬아슬하게 ac가 뜨더라구요

이거 왜그러는걸까요?

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

#define  max_n 1000
#define  max_v  2 * (max_n)+10
const int start = 0;
const int endd = max_v - 2;
vector<int> arr[max_v];
int c[max_v][max_v];
int f[max_v][max_v];
int n, m;


int main(void)
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(NULL);

	scanf("%d %d", &n, &m);
	//n은 직원 , m은 일개수



	int num, work;

	//직원->일
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &num);

		for (int j = 1; j <= num; j++)
		{
			int x;
			scanf("%d", &x);
			x = x + max_n;
			arr[i].push_back(x);
			arr[x].push_back(i);
			c[i][x] = 1;
		}

		c[start][i] = 1;
		arr[start].push_back(i);
		arr[i].push_back(start);
	}

	//일->끝
	for (int i = 1; i <= m; i++)
	{
		work = i + max_n;
		c[work][endd] = 1;
		arr[work].push_back(endd);
		arr[endd].push_back(work);
	}


	int total = 0;
	int prev[max_v];

	while (true)
	{
		memset(prev, -1, sizeof(prev));
		queue<int> pq;
		pq.push(start);

		while (!pq.empty())
		{
			int now = pq.front();
			pq.pop();

			for (int next : arr[now])
			{
				if (c[now][next] - f[now][next] == 1 && prev[next] == -1)
                    //위 조건의 순서가 바뀌면 ac가 뜹니다 
				{
					pq.push(next);
					prev[next] = now;
					if (next == endd)
						break;
				}
			}
		}

		if (prev[endd] == -1)
			break;



		for (int i = endd; i != start; i = prev[i])
		{
			f[prev[i]][i] ++;
			f[i][prev[i]] --;
		}

		total++;
	}
	printf("%d", total);
	return 0;
}

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

문제

문제

출처

ICPC

시간초과

djghdy 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말