글 읽기 - 알고리즘 질문입니다.

wn1op 6년 전 0

저는 이 문제를 다익스트라를 응용하여서, 기본적으로 shortest path를 찾을 때는 minHeap을 이용해서 거리가 짧은 순으로 찾아가는 것을, 이 문제에서는

1. max Heap을 이용해서 현재 그 노드에 가장 많은 flow를 흘릴 수 있는 노드를 찾는다.

2. shortest path 찾기에서의 현재 찾은 최단 거리와 S'에 들어가는 원소에서의 cost + S'에 들어가는 원소 cost를 비교하여 작은 것으로 갱신 => 이 문제의 경우 min( S'에 들어가는 원소로의 flow, S'에 들어가는 원소에서의 cost)를 현재 찾은 최대 flow와 비교하여 큰 것으로 갱신

이런식으로 해서 s->e로의 max flow route를 찾았습니다. 예제는 잘 계산되고, s에서 다른 모든 점으로의 max flow도 잘 계산되는 것을 확인했습니다. 현재 알고리즘에서 어느부분이 문제가 있을까요? 8%에서 틀렸습니다가 나옵니다.

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

#define INF 2000000
#define MAX_N 100010
#define MAX_M 300010

struct Edges {
	int to_v;
	int cost;
};

vector<Edges> graph[MAX_N];

struct Node {
	int vertex;
	int cost;
};

int min(int a, int b) {
	return (a > b) ? b : a;
}

struct comparator {
	bool operator()(Node i, Node j) {
		return i.cost < j.cost;
	}
};

vector<int> flow(MAX_N);

int findMaxOneFlow(int source, int sink, int vertex_num) {
	priority_queue<Node, vector<Node>, comparator> maxHeap;

	fill(flow.begin(), flow.end(), -1);

	flow[source] = INF;
	maxHeap.push({ source, INF });

	while (!maxHeap.empty()) {
		Node node = maxHeap.top();
		maxHeap.pop();

		for (vector<Edges>::iterator itr = graph[node.vertex].begin(); itr != graph[node.vertex].end(); itr++) {
			int maxFlow = min(flow[node.vertex], itr->cost);

			if (flow[itr->to_v] == -1) {
				flow[itr->to_v] = maxFlow;
				maxHeap.push({ itr->to_v, maxFlow });
			}
			else if (flow[itr->to_v] < maxFlow) {
				flow[itr->to_v] = maxFlow;
			}
		}
	}

	return flow[sink];
}

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	int s, e;
	scanf("%d %d", &s, &e);
	for (int i = 1; i <= m; i++) {
		int v1, v2, cost;

		scanf("%d %d %d", &v1, &v2, &cost);

		graph[v1].push_back({ v2,cost });
		graph[v2].push_back({ v1,cost });
	}

	int result = findMaxOneFlow(s, e, n);
	if (result == -1 || result == INF)
		result = 0;

	printf("%d\n", result);

	return 0;
}

wn1op 6년 전 0

같은 vertex간에 다른 무게제한을 가진 다리가 여러개 있을 경우를 고려하여 각 edge vector를 cost를 기준으로 내림차순으로 정렬하여, 같은 vertex 간에서 가장 큰 무게제한을 가진 다리가 반드시 먼저 고려되도록 수정하였습니다. 하지만, 동일한 8%에서 틀렸습니다가 나오네요 ㅠㅠ

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

문제

문제

출처

ICPC

알고리즘 질문입니다.

wn1op 6년 전 0

wn1op 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말