【题目描述】
给定一个 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 次，那么就一定存在负圈。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = ;
const int maxx = 1e6 + ;
const double INF = 1e300; //double型一个很大的数
vector<int>v[maxn];
vector<double>c[maxn];
int cnt[maxn], vis[maxn]; //cnt[]入队次数
double dis[maxn];
int n, m;
void init()
{
for(int i = ; i < maxn; ++i)
{
v[i].clear(); c[i].clear();
}
}
bool spfa(double x)
{
for(int i = ; i < maxn; ++i) { cnt[i] = vis[i] = ; dis[i] = INF;}
queue<int>q;
for(int i = ; i <= n; ++i)
{
q.push(i); cnt[i]++; dis[i] = ;
} while(!q.empty())
{
int now = q.front(); q.pop();
vis[now] = ;
for(int i = ; i < v[now].size(); ++i)
{
if(dis[now] + c[now][i] - x < dis[v[now][i]]) //别忘减去 x！！
{
dis[v[now][i]] = dis[now] + c[now][i] - x;
if(!vis[v[now][i]])
{
q.push(v[now][i]); vis[v[now][i]] = ; cnt[v[now][i]]++; if(cnt[v[now][i]] > n) return true;
}
}
}
}
return false;
}
int main()
{
int T; scanf("%d", &T);
for(int kase = ; kase <= T; ++kase)
{
init();
printf("Case #%d: ", kase);
scanf("%d%d", &n, &m);
for(int i = ; i <= m; ++i)
{
int a, b, cost; scanf("%d%d%d", &a, &b, &cost);
v[a].push_back(b);
c[a].push_back(cost);
}
if(!spfa(maxx)) printf("No cycle found.\n"); //不存在负圈
else
{
double L = , R = maxx; //二分法求值
while(R - L > 1e-)
/*因为保留两位小数，所以只用让 L和 R相差小于0.01即可，这里选择0.001
注意：不能写 R == L，因为存在浮点误差，两个double型实数不能相等）*/
{
double mid = (L + R) / ;
if(spfa(mid)) R = mid;
else L = mid;
}
printf("%.2lf\n", L);
}
}
}