글 읽기 - 6086 질문입니다 ㅠㅠ

hjhng125 5년 전 0

저는 맞게 한거 같은데 계속 틀렸습니다. 라고 나옵니다 ㅠㅠ

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

#define MAX 52
#define INF 1e9 + 1

using namespace std;

int n, c[MAX][MAX], f[MAX][MAX];
vector<vector<int> > adj;

int cToI(char c) {
	if (c <= 'Z') {
		return c - 'A';
	}
	return c - 'a' + 26;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	adj.resize(MAX);
	for (int i = 1; i <= n; ++i) {
		char U, V;
		int b;
		cin >> U >> V >> b;
		int u = cToI(U);
		int v = cToI(V);
		adj[u].push_back(v);
		adj[v].push_back(u);
		c[u][v] += b;
	}
	int S = cToI('A');
	int T = cToI('Z');
	int total = 0;
	while (1) {
		vector<int> prev(MAX, -1);
		queue<int> q;
		q.push(S);
		prev[S] = S;
	
		while (!q.empty() && prev[T] == -1) {
			int here = q.front();
			q.pop();
			for (auto next : adj[here]) {
				if (c[here][next] - f[here][next] > 0 && prev[next] == -1) {
					prev[next] = here;
					q.push(next);
					
				}
			}
		}
		if (prev[T] == -1)
			break;
		int minFlow = INF;
		for (int i = T; i != S; i = prev[i])
			minFlow = min(minFlow, c[prev[i]][i] - f[prev[i]][i]);
		for (int i = T; i != S; i = prev[i]) {
			f[prev[i]][i] += minFlow;
			f[i][prev[i]] -= minFlow;
		}
		total += minFlow;
	}
	cout << total << "\n";

	return 0;
}

tlarbvkf 5년 전 0

배열 c가 용량을 나타내는거 같은데 파이프가 양방향이기 때문에 c[u][v] += b; 다음에 c[v][u] += b; 도 추가하셔야 할 거 같습니다.

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

문제

문제

출처

ICPC

6086 질문입니다 ㅠㅠ

hjhng125 5년 전 0

tlarbvkf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말