[UVA][解一][spfa+窮舉] 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 |
|
所有狀態紀錄哪個點幾次邊(nd, time)。
對於所有點都做，故需要 O(E*n^3)
#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];
int dis[51][51], used[51][51];
void spfa(int st, int n, double& cut) {
static int i, j;
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
dis[i][j] = oo;
used[i][j] = 0;
}
}
queue<arc> Q;
dis[st][0] = 0;
Q.push(arc(st, 0));
arc A(0,0);
while(!Q.empty()) {
A = Q.front(), Q.pop();
used[A.to][A.w] = 0;
for(vector<arc>::iterator it = g[A.to].begin();
it != g[A.to].end(); it++) {
if(dis[it->to][A.w+1] > dis[A.to][A.w] + it->w) {
dis[it->to][A.w+1] = dis[A.to][A.w] + it->w;
if(!used[it->to][A.w+1]) {
used[it->to][A.w+1] = 1;
Q.push(arc(it->to, A.w+1));
}
}
}
}
for(i = 1; i <= n; i++)
if(dis[st][i] != oo)
cut = min(cut, (double)dis[st][i]/i);
}
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();
while(m--) {
scanf("%d %d %d", &a, &b, &c);
g[a].push_back(arc(b,c));
}
double ans = 0xfffffff;
for(i = 1; i <= n; i++)
spfa(i, n, ans);
printf("Case #%d: ", ++cases);
if(ans == 0xfffffff)
puts("No cycle found.");
else
printf("%.2lf\n", ans);
}
return 0;
}