给定一一个n个点m条边的加权有向图， 平均值最小的回路。

二分答案，对于每个二分的mid 做一次Bellman-Fprd , 假设有k条边组成的回路。 回路上各条边的权值为  w1 , w2 ..wk ，

那么平均值小于mid意味着w1+w2+w3..+wk< k*mid 即：

  （w1 - min）+(w2-mid)+...+(w2-mid)<0；

也就是说 这k条边能组成 一个负环，用 Bellman_Ford 来检查

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 using namespace std; 9 const int maxn = 55; 10 int cmp(double a ,double b){ 11 if(fabs(a-b)<=0.00000001) return 0; 12 return a-b>0?1:-1; 13 } 14 struct Edge{ 15 int from,to; 16 double dist; 17 }; 18 struct BellmanFord{ 19 int n,m; 20 vector
            
              edges; 21 vector
             
               G[maxn]; 22 bool inq[maxn]; 23 double d[maxn]; 24 int p[maxn]; 25 int cnt[maxn]; 26 void inti(int n){ 27 m=0; 28 this->n = n; 29 for(int i=0; i
              

Q; 39 memset(inq, 0, sizeof(inq)); 40 memset(cnt, 0, sizeof(cnt)); 41 for(int i=0; i < n; ++i) { d[i] =0; inq[i] = true; Q.push(i);} 42 while(!Q.empty()){ 43 int u = Q.front(); Q.pop(); 44 inq[u] = false; 45 for(int i=0; i

0){ 48 d[e.to] = d[u] +e.dist; 49 p[e.to] = G[u][i]; 50 if(!inq[e.to]){ 51 Q.push(e.to); inq[e.to] = true; 52 if(++cnt[e.to]>n) return true; 53 } 54 } 55 } 56 } 57 return false; 58 } 59 }solver; 60 bool test(double x){ 61 for(int i=0; i

1e-3){ 90 double M = L+(R-L)/2; 91 if(test(M)){ 92 R=M; 93 }else { 94 L=M; 95 } 96 } 97 printf("%.2lf\n",L); 98 } 99 100 }101 return 0;102 }