题目链接:

题意:

给你一个有向图，问你定义一个环的平均值为这个环上所有边的平均值，问你最小的环的平均值是多少

题解:

二分答案：若当前的二分值是mid，让所有的边都减去这个值，如果此时图中出现负环，则说明有环的平均值比这个更小

假设一个包含k条边的回路，回路上各条边的权值为w1,w2……wk，那么平均值小于mid意味着 w1+w2+……wk< k* mid即：

（w1-mid)+(w2-mid)+……(wk-mid)<0

有负环，当前平均值就大了

注意图可能不连通，每个没访问过得点都spfa判一遍

代码:

1 #include 
      
        2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){10     ll x=0,f=1;char ch=getchar();11     while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}13     return x*f;14 }15 //16 const int maxn = 50+10;17 double eps = 1e-6;18 19 int n,m;20 21 vector
       
        
          > G[maxn];22 int vis[maxn],inq[maxn],cnt[maxn];23 double d[maxn];24 25 bool spfa(int u){26     MS(inq);MS(cnt);27     for(int i=0; i<=n; i++) d[i] = INF;28     queue
         
           q;29     q.push(u),inq[u]=1,d[u]=0;30     while(!q.empty()){31         int now = q.front(); q.pop(); inq[now] = 0;32         vis[now] = 1;33         for(int i=0; i<(int)G[now].size(); i++){34             int v = G[now][i].first; double w = G[now][i].second;35             if(d[v] > d[now]+w){36                 d[v] = d[now]+w;37                 if(inq[v]) continue;38                 inq[v] = 1;39                 q.push(v);40                 cnt[v]++;41                 if(cnt[v] > n) return true;42             }43         }44     }45     return false;46 }47 48 bool check(double x){49     for(int i=1; i<=n; i++)50         for(int j=0; j<(int)G[i].size(); j++)51             G[i][j].second -= x; // 让所有的边都减去mid，如果此时图中出现负环，则说明有环的平均值比这个更小52     MS(vis);53     bool flag;54     for(int i=1; i<=n; i++){55         if(!vis[i]) // 图可能不连通，每个没访问过得点都判一遍56             flag = spfa(i);57         if(flag) break;58     }59 60     for(int i=1; i<=n; i++)61         for(int j=0; j<(int)G[i].size(); j++)62             G[i][j].second += x;63 64     return flag; // flag为true 就是有负环，当前平均值就大了65 }66 67 68 int main(){69     int T = read();70     for(int cas=1; cas<=T; cas++){71         for (int i = 0; i <= n; i++)G[i].clear();72         scanf("%d%d",&n,&m);73         for(int i=1; i<=m; i++){74             int u,v; double w;75             scanf("%d%d%lf",&u,&v,&w);76             G[u].push_back(MP(v,w));77         }78 79         double L=0,R=1e7,ans=1e7;80         while((R-L)>eps){81             double mid = (L+R)/2;82             if(check(mid)) ans=mid,R=mid-eps;83             else L=mid+eps;84         }85         if(abs(ans-1e7)