【题目描述】
给定一个 n 个点 m 条边的加权有向图，求平均权值最小的回路。
【输入格式】
输入第一行为数据组数 T 。每组数据第一行为图的点数 n 和边数 m (n ≤ 50)。以下 m 行每行3个整数 u, v, w, 表示有一条从 u 到 v 的有向边，权值为 w。输入没有自环。
【输出格式】
对于每组数据，输出平均最小值，并保留2位小数。如果误解，输出 "No cycle found."。
这道题吧，我觉得使用二分法求解不错。首先才一个值 mid，只需要判断是否存在平均值小于 mid 的回路。那么如何判断呢？假设存在一个包含 k 条边的回路，回路上各条边的权值为 w₁, w₂, w₃......（k 个），那么平均值小于 mid 意味着 w₁ + w₂ + w₃ +...... (k 个)< k * mid，即：
(w₁ - mid) + (w₂ - mid) + (w₃ - mid) + ......(k 组) < 0
这么看来，只要把每条边 (a, b) 的权 w(a, b) 变成 w(a, b) - mid，在判断图中是否有负全回路（负圈）即可。至于如何盘负圈，用 spfa 搜一遍图，若一个结点入队 n 次，那么就一定存在负圈。
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 const int maxn = 55; 9 const int maxx = 1e6 + 1; 10 const double INF = 1e300; //double型一个很大的数 11 vector<int>v[maxn]; 12 vector<double>c[maxn]; 13 int cnt[maxn], vis[maxn]; //cnt[]入队次数 14 double dis[maxn]; 15 int n, m; 16 void init() 17 { 18 for(int i = 0; i < maxn; ++i) 19 { 20 v[i].clear(); c[i].clear(); 21 } 22 } 23 bool spfa(double x) 24 { 25 for(int i = 0; i < maxn; ++i) { cnt[i] = vis[i] = 0; dis[i] = INF;} 26 queue<int>q; 27 for(int i = 1; i <= n; ++i) 28 { 29 q.push(i); cnt[i]++; dis[i] = 0; 30 } 31 32 while(!q.empty()) 33 { 34 int now = q.front(); q.pop(); 35 vis[now] = 0; 36 for(int i = 0; i < v[now].size(); ++i) 37 { 38 if(dis[now] + c[now][i] - x < dis[v[now][i]]) //别忘减去 x！！ 39 { 40 dis[v[now][i]] = dis[now] + c[now][i] - x; 41 if(!vis[v[now][i]]) 42 { 43 q.push(v[now][i]); vis[v[now][i]] = 1; cnt[v[now][i]]++; 44 45 if(cnt[v[now][i]] > n) return true; 46 } 47 } 48 } 49 } 50 return false; 51 } 52 int main() 53 { 54 int T; scanf("%d", &T); 55 for(int kase = 1; kase <= T; ++kase) 56 { 57 init(); 58 printf("Case #%d: ", kase); 59 scanf("%d%d", &n, &m); 60 for(int i = 1; i <= m; ++i) 61 { 62 int a, b, cost; scanf("%d%d%d", &a, &b, &cost); 63 v[a].push_back(b); 64 c[a].push_back(cost); 65 } 66 if(!spfa(maxx)) printf("No cycle found. "); //不存在负圈 67 else 68 { 69 double L = 0, R = maxx; //二分法求值 70 while(R - L > 1e-3) 71 /*因为保留两位小数，所以只用让 L和 R相差小于0.01即可，这里选择0.001 72 注意：不能写 R == L，因为存在浮点误差，两个double型实数不能相等）*/ 73 { 74 double mid = (L + R) / 2; 75 if(spfa(mid)) R = mid; 76 else L = mid; 77 } 78 printf("%.2lf ", L); 79 } 80 } 81 }