글 읽기 - 반례를 찾고 싶습니다

movie_jo 6년 전 0

아직 유량쪽은 감을 잘 못잡아서.. a 에서 b 까지 다 연결해야 하는거 보고 지레짐작으로 시간초과 날 것 같아서 일부러 다른 방법을 생각하다가 (현재 그냥 다 연결해서 맞추긴 했습니다)

i 번째 사람이 a에서 b 까지를 요청하면
i 번째 사람과 a번째 책을 연결하고
a번째 책부터 b번째 책 까지 바로 뒷 책이랑 연결하고(109 ~ 112 라인)
겹치는 부분은 capacity 증가시키는 방식으로 했는데요

이렇게 하면 플로우가 a로 들어가서 빈데로 들어가고 다른 플로우가 반대 방향으로 가면서 최대 나올 것 같았는데...

예제나 다른 질문에서 나온 인풋 같은거 넣어도 다 제대로 나오는데 어떤 예외가 있는지 모르겠습니다

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

#define ARR_SIZE 2002

#define SRC 0
#define SNK 2001

#define MAX_FLOW 2147483647

vector<int> v[ARR_SIZE];
int c[ARR_SIZE][ARR_SIZE];
int f[ARR_SIZE][ARR_SIZE];
int  visit[ARR_SIZE];
int parent[ARR_SIZE];

void conn (int i, int j, int capa)
{
	if (c[i][j])
	{
		c[i][j] += capa;
		return;
	}

	v[i].push_back(j);
	v[j].push_back(i);
	c[i][j] = capa;
	c[j][i] = f[i][j] = f[j][i] = 0;
}

int sol ()
{
	int sum = 0;

	for (int t = 1; ; t++)
	{
		queue<int> q;

		q.push(SRC);
		visit[SRC] = t;

		while (visit[SNK] != t && !q.empty())
		{
			int uu = q.front(); q.pop();

			for (int i = 0; i < v[uu].size(); i++)
			{
				int vv = v[uu][i];

				if (visit[vv] == t) continue;

				if (c[uu][vv] - f[uu][vv] > 0)
				{
					parent[vv] = uu;
					q.push(vv);
					visit[vv] = t;
				}
			}
		}

		if (visit[SNK] != t) break;

		int max_flow = MAX_FLOW;

		for (int i = SNK; i != SRC; i = parent[i])
			max_flow = min(max_flow, c[parent[i]][i] - f[parent[i]][i]);

		for (int i = SNK; i != SRC; i = parent[i])
		{
			f[parent[i]][i] += max_flow;
			f[i][parent[i]] -= max_flow;
		}

		sum += max_flow;
	}

	return sum;
}

int main (void)
{
	int T;

	scanf ("%d", &T);

	while (T--)
	{
		for (int i = 0; i < ARR_SIZE; i++)
		{
			v[i].clear();
			visit[i] = 0;

			for (int j = 0; j < ARR_SIZE; j++)
				c[i][j] = f[i][j] = 0;
		}

		int N, M;

		scanf ("%d %d", &N, &M);

		for (int i = 1; i <= M; i++)
		{
			int a, b; scanf ("%d %d", &a, &b);

			conn (i, M + a, 1);

			for (int j = a; j < b; j++)
				conn (M + j, M + j + 1, 1);
		}

		for (int i = 1; i <= M; i++)
			conn (SRC, i, 1);

		for (int i = 1; i <= N; i++)
			conn (M + i, SNK, 1);

		printf ("%d\n", sol());
	}
}