题目链接
题意：给你一个有向图，问你定义一个环的平均值为这个环上所有边的平均值，问你最小的环的平均值是多少。
解题思路：我们可以[二分答案]，再用[SPFA]来check。
check方法：设最小环有k条边，Wi为第i条边的边权，猜测值为mid，那么有
(W1+W2+…+Wk) / k < mid
(W1+W2+…+Wk) < mid * k
(W1-mid)+(W2-mid)+…+(Wk-mid)<0
我们把每一条边权值都减去mid，再判断图中是否出现了负环。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define Inf 100000000
using namespace std;
const int N = 55;
struct Edge{int u, v;double dist;Edge(int u, int v, double dist):u(u),v(v),dist(dist){}
};
struct SPFA{int n, m;double d[N];bool inq[N];int cnt[N];vector<Edge> edges;vector<int> G[N];void init(int n){this->n=n;for ( int i=1; i<=n; i++ ) G[i].clear();edges.clear();} void addeage(int u, int v, double w){edges.push_back(Edge(u,v,w));m=edges.size();G[u].push_back(m-1);}bool spfa(int s){queue<int> Q;for ( int i=1; i<=n; i++ ) d[i]=Inf, inq[i]=0, cnt[i]=0;d[s]=0;Q.push(s);while( !Q.empty() ){int u=Q.front(); Q.pop();inq[u]=false;for ( int i=0; i<G[u].size(); i++ ){Edge& e=edges[G[u][i]];if( d[e.v]>d[u]+e.dist ){d[e.v]=d[u]+e.dist;if( !inq[e.v] ){inq[e.v]=1;Q.push(e.v);if( ++cnt[e.v]==n ) return true;}}}}return false; }
}S;
int n, m;
bool binary(double x){for ( int i=0; i<S.m; i++ ) S.edges[i].dist-=x;bool cnt=false;for ( int i=1; i<=n; i++ ) if( S.spfa(i) ){cnt=true;break;}for ( int i=0; i<S.m; i++ ) S.edges[i].dist+=x;return cnt;
}int main(){int T;scanf("%d", &T);for ( int k=1; k<=T; k++ ){scanf("%d%d", &n, &m );S.init(n);double ub;for ( int i=1; i<=m; i++ ){int u, v;double w;scanf("%d%d%lf", &u, &v, &w );ub=max(ub,w);S.addeage(u,v,w);}printf("Case #%d: ", k);if( !binary(ub+1.0) ) printf("No cycle found.\n");else {double L=0, R=ub;while( R-L>1e-3 ){double M = L+(R-L)/2;if( binary(M) ) R=M;else L=M;}printf("%.2lf\n", L);} }
}