글 읽기 - 어느부분에서 틀린건지 감을 못잡겠네요

i_chacha 4년 전 0

반례들은 검색해본 것들은 다 맞다고 나오는데 뭐가 잘못된 걸까요.

알파벳 갯수가 얼마되지 않아서 그냥 아스키 코드값으로 index 하도록 했는데요..

조언 좀 부탁드립니다. 문제를 잘못 이해한건지..

반례도 알려주실 수 있다면 감사드려요

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, result;
vector <int> v[710];
int c[710][710];
int f[710][710];
int d[710];
const int INF = 1e9;

void inputData() {
	char t1, t2;
	int  t3;
	
	cin >> N;
	for(int i=0; i<N; i++) {
		cin >> t1 >> t2 >> t3;
		v[t1].push_back(t2);
		v[t2].push_back(t1);
		c[t1][t2] = t3;
		c[t2][t1] = t3;
	}
}

void maxFlow(int start, int end) {
	int result = 0;
	while(1){
		fill(d, d+710, -1);
		queue <int> q;
		q.push(start);
		
		while(!q.empty()) {
			int x = q.front(); q.pop();
			
			for(int i=0; i<v[x].size(); i++) {
				int y = v[x][i];
				
				if(c[x][y]-f[x][y] > 0 && d[y] == -1) {
					q.push(y);
					d[y] = x;
					if(y == end) break;
				}
			}
		}
		
		if(d[end] == -1) break;
		
		int flow = INF;
		
		for(int i=end; i!=start; i=d[i]) {
			flow = min(flow, c[d[i]][i] - f[d[i]][i]);
		}
		
		for(int i=end; i!=start; i=d[i]) {
			f[d[i]][i] += flow;
			f[i][d[i]] -= flow;
		}
		result += flow;
	}
	
	printf("%d\n", result);
}


int main(void) {
	inputData();
	maxFlow('A', 'Z');
	return 0;
}

3587jjh 4년 전 1

같은 간선이 여러번 들어올땨에 대한 고려가 안되어있습니다

rhtkdwls 3년 전 0

혹시 시작점과 끝점이 같은 파이프도 고려하셨나요?

저도 계속 틀리다가 혹시 시작점과 끝점이 같은(ex. 'C' -> 'C') 파이프가 있지 않을가 하고 예외처리해주니깐 AC를 받을 수 있었습니다.

"파이프가 시작점과 끝점이 같은 게 존재하나?" 라고 자문해봤는데, 누군가가 "파이프를 잘 구부리면 되지 않겠냐?" 고 말한다면 그것도 뭐 맞는 말인 것 같습니다..

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

문제

문제

출처

ICPC

어느부분에서 틀린건지 감을 못잡겠네요

i_chacha 4년 전 0

3587jjh 4년 전 1

rhtkdwls 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말