uva11090 Bellman-Ford 运用

给定一一个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 <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <string.h>
  5 #include <vector>
  6 #include <queue>
  7 #include <cmath>
  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<Edge> edges;
 21      vector<int> 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<n; ++i ) G[i].clear();
 30         edges.clear();
 31      }
 32      void AddEdge(int form, int to, double dist){
 33         edges.push_back((Edge){form,to,dist});
 34         m =edges.size();
 35         G[form].push_back(m-1);
 36      }
 37      bool negativeCycle(){
 38          queue<int> 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<G[u].size(); i++){
 46                 Edge &e = edges[G[u][i]];
 47                 if(cmp(d[e.to] , d[u] + e.dist)>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<solver.m; i++){
 62         solver.edges[i].dist-=x;
 63      }
 64      bool ret = solver.negativeCycle();
 65      for(int i= 0; i<solver.m; i++)
 66          solver.edges[i].dist+=x;
 67      return ret;
 68 }
 69 int main()
 70 {
 71    int T;
 72    scanf("%d",&T);
 73    for(int kase =1; kase<=T; kase++){
 74        int n,m;
 75        scanf("%d%d",&n,&m);
 76        solver.inti(n);
 77        int ub =0;
 78        while(m--){
 79           int u,v,w;
 80           scanf("%d%d%d",&u,&v,&w); u--,v--; ub= max(ub,w);
 81           solver.AddEdge(u,v,w);
 82        }
 83        printf("Case #%d: ",kase);
 84        double ans = ub;
 85        if(!test(ub+1)){
 86          printf("No cycle found.
");
 87        }else{
 88             double L =0,R= ub;
 89             while(R-L>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
",L);
 98        }
 99 
100    }
101     return 0;
102 }