글 읽기 - 고수님들 지적 한번만 해주시면 감사하겠습니다 ㅜㅜ

shs0911 1년 전 0

Ford-Fulkerson 알고리즘으로 DFS와 결합하여 한번 짜봤습니다.

예제나 질문 게시판 반례는 잘 돌아갑니다.

혹시 어떤점을 간과한지 알려주시면 감사하겠습니다!

#include <bits/stdc++.h>

#define MAX 100
#define INF 99999999

using namespace std;

int n;
int c[MAX][MAX], f[MAX][MAX], vis[MAX];
int adj[MAX][MAX];

int dfs(int a, int T, int flow)
{
	if(vis[a])
		return 0;
	vis[a] = 1;
	
	if(a == T)
		return flow;
	
	for(int i=1; i<=58; i++)
	{
		if(!adj[a][i] || vis[i])
			continue;
		int now_flow = c[a][i] - f[a][i];
		if(now_flow <= 0)
			continue;
		
		int result = dfs(i, T, min(flow, now_flow));
		if(result)
		{
			f[a][i] += result;
			f[i][a] -= result;
			adj[i][a] = 1;
			return result;
		}
	}
	return 0;
}

int maxflow(int S, int T)
{
	int result = 0;
	while(1)
	{
		memset(vis, 0, sizeof(vis));
		int flow = dfs(S, T, INF);
		if(!flow)
			break;
		result += flow;
	}
	return result;
}

int main(void)
{
	cin >> n;
	
	for(int i=0; i<n; i++)
	{
		char u, v;
		int cap;
		cin >> u >> v >> cap;
		c[u-64][v-64] = cap;
		adj[u-64][v-64] = 1;
	}
	
	cout << maxflow(1, 26);
}

shs0911 1년 전 0

중복된 간선을 갱신하고 자기 자신에게 연결된 노드를 무시하는 예외 처리를 해줬더니 통과되었습니다.

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

문제

문제

출처

ICPC

고수님들 지적 한번만 해주시면 감사하겠습니다 ㅜㅜ

shs0911 1년 전 0

shs0911 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말