글 읽기 - 최대 유량 문제 질문입니다 ㅠㅠ 반례가 뭐가 있을까요?

mozzi01331 4년 전 0

아래와 같이 코드를 작성했는데 문제를 검색해서 나오는 반례는 다 통과를 해서요ㅠㅠ 어떤 부분을 고려하지 못한 것인지 궁금합니다

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int INF = 987654321;

int N;
vector<int> map[702];
int capacity[702][702];
int flow[702][702];

int min(int a, int b) {
	if (a > b) {
		return b;
	}
	else {
		return a;
	}
}

int ctoi(char pipeIdx) {
	return pipeIdx - 'A';
}

int networkFlow(int source, int sink) {
	int totalFlow = 0;
	memset(flow, 0, sizeof(flow));

	while (true) {
		vector<int> parent(702, -1);
		queue<int> q;

		parent[source] = source;
		q.push(source);

		while (!q.empty() && parent[sink] == -1) {
			int tempP = q.front();
			q.pop();

			//cout << "tempP is " << tempP << endl;
			//이게 배열이면 안됨!!! 12345가 아니라 1234 26 이렇게도어있으니까~~ 
			for (int nextP : map[tempP]) {
				if (capacity[tempP][nextP] - flow[tempP][nextP] > 0
					&& parent[nextP] == -1) {
					q.push(nextP);
					parent[nextP] = tempP;
				}
			}
		}
		//증가경로가 없는 경우
		if (parent[sink] == -1) {
			break;
		}

		int amount = INF;
		//보낼 유량 결정
		for (int p = sink; p != source; p = parent[p]) {
			amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
		}
		for (int p = sink; p != source; p = parent[p]) {
			flow[parent[p]][p] += amount;
			flow[p][parent[p]] -= amount;
		}

		totalFlow += amount;
	}

	return totalFlow;
}

int main() {
	char s, d;
	int tempC;
	int source = ctoi('A');
	int sink = ctoi('Z');

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> s >> d >> tempC;
		
		capacity[ctoi(s)][ctoi(d)] += tempC;
		map[ctoi(s)].push_back(ctoi(d));
		map[ctoi(d)].push_back(ctoi(s));
	}

	cout << networkFlow(source, sink) << endl;

	return 0;
}

3587jjh 4년 전 1

양방향 그래프인데 용량을 한쪽만 더하셨네요

mozzi01331 4년 전 0

아............. ㅠㅠ 감사합니다!!!!

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

문제

문제

출처

ICPC

최대 유량 문제 질문입니다 ㅠㅠ 반례가 뭐가 있을까요?

mozzi01331 4년 전 0

3587jjh 4년 전 1

mozzi01331 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말