글 읽기 - 에드먼드 카프로 해도 시간초과가 나는 이유가 궁금합니다

wiz9243 5년 전 0

어디에 문제가 있는 걸까요??ㅜ

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 30
#define INF 1001
	
int f[MAX][MAX];
int c[MAX][MAX];
int pre[MAX];
vector<int> adj[MAX];

int maximum_flow(int s, int e) {
	int result = 0;

	while ( 1 ) {
		fill(pre, pre + MAX - 1, -1);
		
		queue<int> q;
		q.push(s);

		while ( !q.empty() ) {
			int now = q.front();
			q.pop();

			for ( int i = 0; i < adj[now].size(); i++ ) {
				int next = adj[now][i];

				if ( pre[i] == -1 && c[now][next] - f[now][next] > 0 ) {
					q.push(next);
					pre[next] = now;
					if ( next == e )break;
				}
			}
		}

		if ( pre[e] == -1 )break;

		int flow = INF;
		for ( int i = e; i != s; i = pre[i] ) {
			flow = min(flow, c[pre[i]][i] - f[pre[i]][i]);
		}

		for ( int i = e; i != s; i = pre[i] ) {
			f[pre[i]][i] += flow;
			f[i][pre[i]] -= flow;
		}
		
		result += flow;
	}

	return result;
}

int main() {
	int n; cin >> n;
	for ( int i = 0; i < n; i++ ) {
		char c1, c2; int k;
		scanf(" %c %c %d", &c1, &c2, &k);
		
		int s, e;
		if ( c1 < 97 )s = c1 - 64;
		else s = c1 - 96;
		if ( c2 < 97 )e = c2 - 64;
		else e = c2 - 96;

		adj[s].push_back(e);
		adj[e].push_back(s);
		c[s][e] += k;
	}
	cout << maximum_flow(1, 26);
}

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

문제

문제

출처

ICPC

에드먼드 카프로 해도 시간초과가 나는 이유가 궁금합니다

wiz9243 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말