글 읽기 - 어디가 틀린걸까요?

lgioi45 7년 전 0

포트 풀커슨 알고리즘으로 접근했는데요.

주어진 예제에서는 답이 나오는데 제출하면 틀렸다고 하네요.

어디가 잘못된건지 조언 부탁드립니다.

#include "stdio.h"
#include "string.h"
#include <vector>
#include <queue>
using namespace std;

#define INF 987654321
#define min(a,b)(a<b?a:b)

int N, P, flow[402][402];
vector<int> adj[402];
int capacity[402][402];

void makeEdge(int s, int e, int w){
	adj[s].push_back(e);
	adj[e].push_back(s);
	capacity[s][e] += w;
}
int ford(int s, int t){
	int ret = 0;
	while(1){
		int prev[205];
		memset(prev, -1, sizeof(prev));
		queue<int> q;
		q.push(s);
		while(!q.empty() && prev[t] == -1){
			int u = q.front();
			q.pop();
			for(int i=0; i<adj[u].size(); i++){
				int v = adj[u][i];
				if(capacity[u][v] - flow[u][v] > 0 && prev[v] == -1){
					q.push(v);
					prev[v] = u;
				}
			}
		}
		if(prev[t] == -1) break;
		int amount = INF;
		for(int u=t; u!=s; u=prev[u])
			amount = min(amount, capacity[prev[u]][u]-flow[prev[u]][u]);
		for(int u=t; u!=s; u=prev[u]){
			flow[prev[u]][u] += amount;
			flow[u][prev[u]] -= amount;
		}
		ret += amount;
	}
	return ret;
}
int main(){
	scanf("%d %d", &N, &P);
	int s = 1, t = 2;
	for(int i=0; i<P; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		makeEdge(u, v, 1);
	}
	printf("%d\n", ford(s, t));
	return 0;
}

isku 7년 전 3

7달전 오래된 질문이지만...

문제의 조건에서 각 정점은 한번만 갈 수 있다고 나와있습니다.

이점을 고려해주셔야 합니다.

5 6
1 5
1 4
4 5
3 4
4 2
3 2

위 테스트 케이스의 답은 1인데 주어진 소스에서는 2를 낼꺼라 생각되네요. (컴파일 해보지는 않았습니다)

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

문제

문제

출처

ICPC

어디가 틀린걸까요?

lgioi45 7년 전 0

isku 7년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말