글 읽기 - 에드몬드 카프 BFS탐색과 동시에 유량값을 갱신하면 안되나요?

previc1 5년 전 0

제 코드 36번째 줄에

q.push(make_pair(i, min(cost, cap[now][i] - flow[now][i])));

로직을 넣어서 bfs탐색과 동시에 가능한 이동가능한 최대유량을 계산하려고 했더니 WA가 나오네요.

반면에 bfs탐색 후 경로를 역추적하면서 최대유량값을 계산하면 AC를 받는데.. 탐색하면서 유량을 계산하면 안되는 케이스는 뭐가있나요?

#include <stdio.h>
#include <algorithm>
#include <queue>
#define MAXN 1000004

using namespace std;

__inline int min(int x, int y){ return x < y ? x : y; }
int cap[60][60];
int flow[60][60];
int par[60];
int a,b,n,f;
int ctoi(char x){
	return x <= 'Z' ? x - 'A' + 26 : x - 'a';
}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf(" %c %c %d", &a, &b, &f);
		cap[ctoi(a)][ctoi(b)] += f;
		cap[ctoi(b)][ctoi(a)] += f;
	}
	int Ans = 0;
	while(1){
		queue<pair<int, int>> q;
		q.push(make_pair(ctoi('A'), MAXN));
		int cost=0;
		for (int i = 0; i <= ctoi('Z'); i++)
			par[i] = -1;
		while (q.size() && par[ctoi('Z')] == -1){
			int now = q.front().first;
			cost = q.front().second;
			q.pop();
			for (int i = 0; i <= ctoi('Z'); i++){
				if (cap[now][i] - flow[now][i] > 0 && par[i]==-1){
					q.push(make_pair(i, min(cost, cap[now][i] - flow[now][i])));
					par[i] = now;
				}
			}
		}
		if (par[ctoi('Z')] == -1) break;
		for (int i = ctoi('Z'); i != ctoi('A'); i=par[i]){
			flow[i][par[i]] -= cost;
			flow[par[i]][i] += cost;
		}
		Ans += cost;
	} 
	printf("%d\n", Ans);
}

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

문제

문제

출처

ICPC

에드몬드 카프 BFS탐색과 동시에 유량값을 갱신하면 안되나요?

previc1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말