题目描述
小C旅行到了美丽的x市。热爱oi的小C把x市分成了n个建筑物和m条双向街道，每一条街道都有一个通过时间，每个建筑物都有一个观赏值v。接着小C就在想了，如果我从任意一个点出发，经过至少两个点（包括出发点）后回到出发点，那么我能得到的最大平均观赏值是多少。平均观赏值指的是总观赏值/总耗费时间。你可以理解成观赏是不需要耗费时间的，且若多次到达同一建筑物，观赏值只会被计算一次。但小C还要和他的好朋友们开黑打农药，于是他就把这个又简单又无聊的问题交给了准备参加NOIP的你。
思路
用val表示观赏值，cost表示花费
题目让我们求出 $\frac{\sum{val}}{\sum{cost}} = ans$ 并使ans最大
我们可以将这个进行变形为 $\sum{val} - ans * \sum{cost} = 0$
那么我们可以二分ans并计算什么时候离0最接近，如果我们找到了一个负环，我们就让r向mid逼近
如果找到了一个正环我们就让l逼近并更新ans
这里用spfa来判断环的存在就可以了
#include#include #include #include using namespace std; #define fill(x, y) memset(x, y, sizeof(x)) #define maxn 1001 #define maxm 5001 #define INF 0x7f7f7f7f struct edge { int to, w, next; }e[maxm]; int ls[maxm], a[maxn], n, m, tot[maxn]; double state[maxn], mid; bool fl[maxn], exits[maxn]; int spfa(int x) { fill(state, -INF); fill(exits, 0); fill(tot, 0); queue t; t.push(x); exits[x] = 1; fl[x] = 1; state[x] = 0; while (!t.empty()) { int now = t.front(); t.pop(); for (int i = ls[now]; i; i = e[i].next) { double tt = a[e[i].to] - mid * e[i].w; if (state[e[i].to] < state[now] + tt) { state[e[i].to] = state[now] + tt; tot[e[i].to]++; if (tot[e[i].to] > n) return true; if (!exits[e[i].to]) { exits[e[i].to] = 1; fl[e[i].to] = 1; t.push(e[i].to); } } } exits[now] = 0; } return false; } int check() { fill(fl, 0); for (int i = 1; i <= n; i++) { if (!fl[i]) { if (spfa(i)) return true; } } return false; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); e[i] = (edge) {y, z, ls[x]}; ls[x] = i; } double l = 0.0, r = 1000.0, ans = 0.0; mid = (l + r) / 2.0; while (r - l > 1e-5) { if (check()) { ans = mid; l = mid + 1e-3; } else r = mid - 1e-3; mid = (l + r) / 2.0; } printf("%.2f\n", ans); }
]]>
Comments NOTHING