글 읽기 - [11377] 열혈강호 C++, 반례가 도저히 생각이 안나네요..

mycool0905 5년 전 0

그림처럼 해가지고 Source에서 가는거랑 Source에서 K로 보내서 가는걸로 했는데, 계속 틀렸다고 나오네요..

뭐가 문제인가요?

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string.h>

constexpr auto WHITE = 0;
constexpr auto BLACK = 1;
constexpr auto NIL = -1;
constexpr auto INF = 9999;

typedef struct node {
	int v;
	int f;
	int c;
}node;

using namespace std;

int N, M, K;
vector<vector<node>> list;
int countOfK = 0;
int color[2002];
int path[2002];

void insert(int u,node uNode, int v, node vNode)
{
	for(unsigned int i=0;i<list[u].size();i++)
		if (list[u][i].v == v)
		{
			list[u][i].c = uNode.c;
			return;
		}
	list[u].push_back(uNode);
	list[v].push_back(vNode);
	
}

bool maxFlow()
{
	queue<int> Queue;
	int u;

	memset(color, WHITE, sizeof(color));
	memset(path, NIL, sizeof(path));

	Queue.push(0);
	color[0] = BLACK;

	while (!Queue.empty())
	{
		u = Queue.front();
		Queue.pop();

		for (unsigned int i = 0; i < list[u].size(); i++)
		{
			if (color[list[u][i].v] == WHITE && list[u][i].c - list[u][i].f > 0)
			{
				path[list[u][i].v] = u;
				if (list[u][i].v == M + N + 1)
					return true;
				color[list[u][i].v] = BLACK;
				Queue.push(list[u][i].v);
			}
		}
	}

	return false;
}

int main()
{
	vector<node> newLine;
	node newNode;
	node newPairNode;
	int input;
	int work;
	int lastPoint;
	int flow;
	stack<pair<int, int>> Stack;

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M >> K;

	for (int i = 0; i <= N + M + 2; i++)
		list.push_back(newLine);

	newNode = { N + M + 2,0,K };
	newPairNode = { 0,0,0 };

	insert(newPairNode.v, newNode, newNode.v, newPairNode); // K Source

	for (int i = 1; i <= N; i++) // Source - L side && K Source - L side
	{
		// Source -> L side
		newNode = { i,0,1 };
		newPairNode = { 0,0,0 };

		insert(newPairNode.v, newNode, newNode.v, newPairNode);

		// K Source -> L side
		newPairNode = { M + N + 2,0,0 };

		insert(newPairNode.v, newNode, newNode.v, newPairNode);
	}

	for (int u = 1; u <= N; u++) // L side - R side
	{
		cin >> input;

		if (input == 0)
			continue;

		for (int i = 0; i < input; i++)
		{
			cin >> work;

			newNode = { work + M,0,1 };
			newPairNode = { u,0,0 };

			insert(newPairNode.v, newNode, newNode.v, newPairNode);
		}
	}

	for (int i = N + 1; i <= N + M; i++) // R side - Sink
	{
		newNode = { N + M + 1,0,1 };
		newPairNode = { i,0,0 };

		insert(newPairNode.v, newNode, newNode.v, newPairNode);
	}

	while (1)
	{

		if (maxFlow() == false)
		{
			int result = 0;

			for (unsigned int i = 0; i < list[0].size(); i++)
				result += list[0][i].f;

			cout << result << "\n";
			break;
		}
		else
		{
			lastPoint = M + N + 1;
			flow = INF;
			while (path[lastPoint] != -1)
			{
				Stack.push(make_pair(path[lastPoint], lastPoint));
				for (unsigned int i = 0; i < list[path[lastPoint]].size(); i++)
					if (list[path[lastPoint]][i].v == lastPoint)
					{
						if (flow > list[path[lastPoint]][i].c - list[path[lastPoint]][i].f)
							flow = list[path[lastPoint]][i].c - list[path[lastPoint]][i].f;
						break;
					}
				lastPoint = path[lastPoint];
			}

			while (!Stack.empty())
			{
				pair<int, int> newStep = Stack.top();
				Stack.pop();

				int newU = newStep.first;
				int newV = newStep.second;
				
				for(unsigned i = 0;i<list[newU].size();i++)
					if (list[newU][i].v == newV)
					{
						list[newU][i].f += flow;
						break;
					}
				for (unsigned i = 0; i<list[newV].size(); i++)
					if (list[newV][i].v == newU)
					{
						list[newV][i].f -= flow;
						break;
					}
			}
		}
	}

	return 0;
}

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

문제

문제

출처

ICPC

[11377] 열혈강호 C++, 반례가 도저히 생각이 안나네요..

mycool0905 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말