백준 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
//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;
}