BOJ 6141

 

백준 6141, SPFA

이것 역시 해결을 못하고 풀이를 본 문제다.

3 가지 포인트를 생각한다면 다음번에는 비슷한 문제를 풀 수 있을것 같다.

1.출발 한 정점으로 다시 돌아와야 한다는 것
2.평균 $X$ 의 flow 로 조건을 만족시킬 수 있는지 결정짓는 문제로 바꿔서 생각해보기
3.평균 $X$ 의 flow와 전체 flow 가 연관된 부등식 만들 수 있는지 생각해보기

다시 돌아와야 한다는 조건은 cycle, 특히 음수 cycle 을 찾는 문제라는 것을 떠올리는데 필요한 조건이다.

cycle을 판정한다는 사실을 관찰했지만, 음수 cycle 과 flow rate 랑 연결시킬 능력이 없었다.

USACO 에 소개된 정해에는 일반적인 Bellman-Ford 알고리즘이 아니라 SPFA 를 사용한 풀이가 있었다.

SPFA 는 queue 를 이용해서 relaxation 을 수행한 정점들에 대해서만 다시 relaxation 을 하므로

모든 정점의 모든 간선에 대한 relaxation 을 수행하는 Bellman-Ford 보다 시간복잡도는 같지만 더 효율적이다.

Source Code

6141링크

//BOJ6141

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define pid pair<int,double>

#define MAXI 1010

int V, E;
double INF = 2000000.0;
double eps = 1e-6;

double fun[MAXI];
vector<vector<pid>> adjList(MAXI);

bool isinQ[MAXI];
double upper[MAXI];
int cnt[MAXI];

bool SPFA(double X) {
	fill(upper, upper + MAXI, INF);
	upper[1] = 0.0;

	memset(isinQ, 0, sizeof(isinQ));
	memset(cnt, 0, sizeof(cnt));

	queue<int> Q;
	Q.push(1);
	isinQ[1] = true;

	while (!Q.empty()) {
		int here = Q.front();
		Q.pop();
		isinQ[here] = false;

		for (int i = 0; i < adjList[here].size(); ++i) {
			int there = adjList[here][i].first;
			double cost = adjList[here][i].second * X - fun[there];
			
			if (upper[there] > upper[here] + cost) {
				upper[there] = upper[here] + cost;
				++cnt[there];
				if (!isinQ[there]) Q.push(there);
				if (cnt[there] >= V) return true;
			}

		}
	}

	return false;
}

double binsearch(double lo, double hi) {
	while (hi - lo > eps) {
		double mid = (lo + hi) / 2;
		if (SPFA(mid)) lo = mid;
		else hi = mid;
	}

	return lo;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> V >> E;

	for (int i = 0; i < V; ++i) {
		cin >> fun[i + 1];
	}

	for (int i = 0; i < E; ++i) {
		int s, e;
		double t;
		cin >> s >> e >> t;
		adjList[s].push_back({ e,t });
	}

	double ans = binsearch(0, 100000.0);

	printf("%.2f", ans);
	
	return 0;

}

wbjeon2k

Pursuite for Progress.

This work is licensed under a Attribution-NonCommercial 4.0 International license. Attribution-NonCommercial 4.0 International