题目链接
解析
考虑我刚学的分数规划。二分答案 \(x\)，问题转化为判定是否有
\[\frac{\sum_{i=1}^{k}w_{c_i,c_{i + 1}}}{k} \le x
\]
变形一下：
\[\sum_{i=1}^{k}(w_{c_i,c_{i + 1}} - x)\le 0
\]
将边权设为 \(w_{c_i,c_{i + 1}} - x\)，要判定的就是是否有负环，SPFA 即可。
时间复杂度 \(O(nm\log w)\)。
代码
/*
*/
#include <bits/stdc++.h>
#define eps 0.0000000001
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 23000 + 5,M = 1000 + 5,P = 2000000,mod = 45989;
int head[N],to[N],nxt[N],e;
double val[N];
double dis[N];
int cnt[N],inq[N];
int n,m;
void add(int u,int v,double w){e++;val[e] = w;to[e] = v;nxt[e] = head[u];head[u] = e;
}
bool chk(double mid){queue<int> q;for(int i=1;i<=n;i++){dis[i] = 0;inq[i] = true;cnt[i] = 0;q.push(i);}while(!q.empty()){int u = q.front();q.pop();inq[u] = false;for(int i=head[u];i;i = nxt[i]){int v = to[i];double w = val[i];if(dis[v] > dis[u] + w - mid){dis[v] = dis[u] + w - mid;if(!inq[v]){inq[v] = true;cnt[v]++;if(cnt[v] >= n + 5){return true;}q.push(v);}}}}return false;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);cin>>n>>m;for(int i=1;i<=m;i++){int u,v;double w;cin>>u>>v>>w;add(u,v,w);}double l = -1e7,r = 1e7;while(r - l > eps){double mid = (l + r) / 2;if(chk(mid)) r = mid;else l = mid;}cout<<fixed<<setprecision(8)<<l;return 0;
}