UVA 11090 Going in Cycle!!——二分+spfa

UVA 11090 Going in Cycle!!——二分+spfa

二分最小平均值，对于一个二分到的值mid，如何判断是否存在平均值小于mid的回路呢？假设存在一个包含k条边的回路，回路上各条边的权值为w1 w2、、、、、、wn，那么平均值小于mid意味着w1+w2+、、、、、、+wn

#include #include #include #include #include #include using namespace std;const int maxn = 100;struct Edge { int from, to; double dist; Edge(int x, int y, double z) : from(x), to(y), dist(z) {}};struct BellmanFord { int n, m; vector edges; vector 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 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] = false; 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] = true; if (++cnt[e.to] > n) return true; } } } } return false; }}solver;bool test(double x) { for (int i = 0; i < solver.m; i++) { solver.edges[i].dist -= x; } bool ret = solver.negativeCycle(); for (int i = 0; i < solver.m; i++) { solver.edges[i].dist += x; } return ret;}int main() { int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { int n, m; scanf("%d %d", &n, &m); solver.init(n); int ub = 0; while (m--) { int u, v, w; scanf("%d %d %d", &u, &v, &w); u--; v--; ub = max(ub, w); solver.addedge(u, v, w); } printf("Case #%d: ", kase); if (!test(ub+1)) printf("No cycle found.\n"); else { double L = 0, R = ub; while (R - L > 1e-3) { double M = L + (R-L)/2; if (test(M)) R = M; else L = M; } printf("%.2lf\n", L); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。