[UVA][解二][二分+負環] 11090 - Going in Cycle!!
|
I I U P C 2 0 0 6 |
|
|
Problem G: Going in Cycle!! |
|
|
Input: standard input Output: standard output |
|
|
|
|
|
You are given a weighted directed graph with n vertices and m edges. Each cycle in the graph has a weight, which equals to sum of its edges. There are so many cycles in the graph with different weights. In this problem we want to find a cycle with the minimum mean.
|
|
|
Input |
|
|
The first line of input gives the number of cases, N. N test cases follow. Each one starts with two numbers n and m. m lines follow, each has three positive number a, b, c which means there is an edge from vertex a to b with weight of c.
|
|
Output |
|
|
For each test case output one line containing “Case #x: ” followed by a number that is the lowest mean cycle in graph with 2 digits after decimal place, if there is a cycle. Otherwise print “No cycle found.”.
|
|
|
Constraints |
|
|
- n ≤ 50 - a, b ≤ n - c ≤ 10000000
|
|
|
Sample Input |
Output for Sample Input |
|
2 |
Case #1: No
cycle found. |
|
|
|
|
Problemsetter: Mohammad Tavakoli Ghinani Alternate Solution: Cho |
|
二分答案，然後將所有邊減去答案，此時檢查是否有存在負環，
以前我都是窮舉點進行 spfa 的迭代，查看是否存在負環 (入隊次數大於 n)
而網路上搜到的是一次放入所有的點去檢查負環，這一點我還必須思考一下。
但我相信是對的。
#include <stdio.h>
#include <vector>
#include <queue>
#define oo 0xfffffff
using namespace std;
struct arc {
int to, w;
arc(int x, int y): to(x), w(y) {}
};
vector<arc> g[51];
double dis[51];
int used[51], inq[51];
int negCycle(int n, double m) {
static int i, tn;
queue<int> Q;
for(i = 1; i <= n; i++) {
dis[i] = 0, used[i] = 1, inq[i] = 0;
Q.push(i);
}
while(!Q.empty()) {
tn = Q.front(), Q.pop();
used[tn] = 0;
for(vector<arc>::iterator it = g[tn].begin();
it != g[tn].end(); it++) {
if(dis[it->to] > dis[tn] + it->w - m) {
dis[it->to] = dis[tn] + it->w - m;
if(!used[it->to]) {
used[it->to] = 1;
Q.push(it->to);
if(++inq[it->to] > n)
return 1;
}
}
}
}
return 0;
}
int main() {
scanf("%*d");
int n, m, i, a, b, c;
int cases = 0;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 1; i <= n; i++)
g[i].clear();
double l = 0, r = 0, mid;
while(m--) {
scanf("%d %d %d", &a, &b, &c);
g[a].push_back(arc(b,c));
if(c > r) r = c;
}
r += 10;
printf("Case #%d: ", ++cases);
if(!negCycle(n, r)) {
puts("No cycle found.");
continue;
}
while(r - l > 1e-4) {
mid = (l+r)/2;
if(negCycle(n, mid))
r = mid;
else
l = mid;
}
printf("%.2lf\n", r);
}
return 0;
}