题目大意
给定一个N个点M条边的带权有向图，求平均值最小的回路。
解法
看到这种题目，喜欢打暴力的我一下就想到：遍历整个图，找到每一个环，然后算出它们的平均值，最后比较出最小值。然而，呃...，会T飞...
既然我们不能暴力找最小值，那还有什么别的办法吗？
我们只需要输出一个最小值就行了，既然不能暴力遍历找环，那我们为何不能直接找答案呢？聪明的你一定想到了，找答案最一流（最高效）的，不就是二分答案吗？
确认了方向，接下来就是实现。
我们假设 \(ans\) 为我们找到的最小值，\(mid\) 为当前找到的值，\(m\) 为 \(mid\) 所在的环的边的条数，\(w_i\) 为 \(mid\) 所在的环的第 \(i\) 条边的边权。
首先:
\(mid = \frac{\sum\limits_{i = 1}^m{w_i}}{m}\)
\(\because mid \ge ans\)
\(\therefore \frac{\sum\limits_{i = 1}^m{w_i}}{m} \ge ans\)
通分一下：
\(\sum\limits_{i = 1}^m{w_i} \ge ans \cdot m\)
移项一下：
\(\sum\limits_{i = 1}^m{w_i} - ans \cdot m \ge 0\)
稍微变一下：
\(\sum\limits_{i = 1}^m{(w_i - ans)} \ge 0\)
这时，我们发现，环中的每一条边的边权减去 \(ans\) 后加起来的和是要大于0的。诶，等等，这不就是判负环吗？
也就是说，我们把每一条边的边权减去我们猜的答案 \(mid\)，只要图中没有负环，就说明这个答案合法，可以猜小一点，反之则猜大。
于是乎，\(\text{check}\) 函数也就慢慢地浮现出来了：SPFA判负环！
做到这里，我们就基本已经做完了这道题，接下来就可以看看我丑陋的代码了。
AC Code
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
struct node
{
int y;
double w;
};
int T, t, n, m, cnt[N];
double dis[N];
bool vis[N];
vector<node> a[N];
void init()
{
for(int i = 1; i <= n; i++)
a[i].clear();
return;
}
bool spfa(double s)
{
memset(cnt, 0, sizeof(cnt));
memset(vis, false, sizeof(vis));
queue<int> q;
for(int i = 1; i <= n; i++)//由于题目不保证图连通，所以是多起点SPFA
{
dis[i] = 0;
q.push(i);
vis[i] = true;
}
while(!q.empty())
{
int x = q.front();
q.pop();
vis[x] = false;
int len = a[x].size();
for(int i = 0; i < len; i++)
{
int y = a[x][i].y;
double w = a[x][i].w - s;//注意这里边权要减去猜的答案
if(dis[x] + w < dis[y])
{
dis[y] = dis[x] + w;
cnt[y] = cnt[x] + 1;
if(cnt[y] >= n)
return true;
if(vis[y])
continue;
q.push(y);
vis[y] = true;
}
}
}
return false;
}
void slove()
{
cin >> n >> m;
init();
double lt = 1e9, rt = -1e9;
for(int i = 1; i <= m; i++)
{
int x, y;
double w;
cin >> x >> y >> w;
a[x].push_back((node){y, w});
lt = min(lt, w), rt = max(rt, w);//取左边界和右边界
}
lt--, rt++;
double q = rt;//处理无解的情况准备的
while(lt + 1e-6 < rt)//注意精度问题
{
double mid = (lt + rt) / 2;
if(spfa(mid))
rt = mid;
else
lt = mid;
}
if(q == rt)//判断是否无解
printf("Case #%d: No cycle found.\n", ++t);//注意输出格式
else
printf("Case #%d: %.2f\n", ++t, rt);
return;
}
int main()
{
cin >> T;
while(T--)
slove();
return 0;
}
完结撒花★,°:.☆(￣▽￣)/:.°★ 。★,°:.☆(￣▽￣)/:.°★ 。