uva11090 Going in Cycle!!
题意：找到图中平均权值最小的回路
思路：假设答案是val 那么图中的边权值减去val，原来的回路便会成为负圈
val的值可以通过二分+spfa判负圈完成
//#pragma warning (disable: 4786)//#pragma comment (linker, "/STACK:16777216")//HEAD#include <cstdio>#include <ctime>#include <cstdlib>#include <cstring>#include <queue>#include <string>#include <set>#include <stack>#include <map>#include <cmath>#include <vector>#include <iostream>#include <algorithm>using namespace std;//LOOP#define FF(i, a, b) for(int i = (a); i < (b); ++i)#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)#define FE(i, a, b) for(int i = (a); i <= (b); ++i)#define FED(i, b, a) for(int i = (b); i>= (a); --i)#define REP(i, N) for(int i = 0; i < (N); ++i)#define CLR(A,value) memset(A,value,sizeof(A))#define CPY(a, b) memcpy(a, b, sizeof(a))#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)//STL#define SZ(V) (int)V.size()#define PB push_back#define EQ(a, b) (fabs((a) - (b)) <= 1e-10)#define ALL(c) (c).begin(), (c).end()//INPUT#define RI(n) scanf("%d", &n)#define RII(n, m) scanf("%d%d", &n, &m)#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)#define RS(s) scanf("%s", s)//OUTPUT#define WI(n) printf("%d\n", n)#define WS(s) printf("%s\n", s)typedef long long LL;typedef unsigned long long ULL;typedef vector <int> VI;const int INF = 100000000;const double eps = 1e-10;const int MAXN = 505;struct Edge{ int from, to; double dist;};struct BellmanFord{ int n, m; vector<Edge> edges; vector<int> G[MAXN]; bool inq[MAXN]; double d[MAXN]; int p[MAXN]; int cnt[MAXN]; void init(int n) { this->n = n; for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void addedge(int from, int to, double dist) { edges.push_back((Edge){from, to, dist}); m = edges.size(); G[from].push_back(m - 1); } bool negativeCycle() { queue<int> Q; memset(inq, 0, sizeof(inq)); memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; i++) { d[i] = 0; inq[0] = true; Q.push(i); } while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for (int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; if (!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; if (++cnt[e.to] > n) return true; } } } } return false; }}bell;bool test(double mid){ REP(i, bell.m) bell.edges[i].dist -= mid; bool ret = bell.negativeCycle(); REP(i, bell.m) bell.edges[i].dist += mid; return ret;}int main(){ int n, m; int maxw; int T; RI(T); FE(kase, 1, T) { RII(n, m); bell.init(n); int a, b; int c; maxw = -INF; REP(i, m) { RIII(a, b, c); maxw = max(maxw, c); a--, b--; bell.addedge(a, b, c); } printf("Case #%d: ", kase); if (!test(maxw + 1)) WS("No cycle found."); else { double L = 0.0, R = maxw; while (R - L > 1e-3) { double mid = (R + L) / 2; if (test(mid)) R = mid; else L = mid; } printf("%.2lf\n", L); } }}