「USACO 2007 Dec. Gold」Sightseeing Cows

给定一张 n1000n\le1000 个点、m5000m\le5000 条边的有向图

每个点都有一个权值 fif_i ,每条边都有一个权值 tit_i

求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大

对答案进行二分,二分的值为 midmid

 ft>mid fmid×t>0 mid×tf<0 \begin{aligned} &\exist\ \frac{\sum f}{\sum t}>mid\\ \Leftrightarrow &\exist\ \sum f-mid\times t>0\\ \Leftrightarrow &\exist\ \sum mid\times t- f<0 \end{aligned}

不能推到第二行式子就开始判

因为负环判定实际上是判是否存在负环

而不是所有环都是负环

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr; using std::cin; using std::cout; using std::endl;
using std::make_pair; using std::pair; typedef pair<int, int> pii;
typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull;
const int N = 1010, M = 5050;
struct Edge{
int t, v;
double w;
} e[M];
std::vector<Edge*> p[N];
int n, f[N], c[N];
double d[N];
bool inq[N];
// negative_loop => 1
int spfa(){
std::queue<int> q;
std::memset(c, 0, sizeof(c));
std::memset(d, 0, sizeof(d));
rep(i, 1, n) q.push(i), inq[i] = 1;
while(q.size()){
int u = q.front(); q.pop();
inq[u] = 0;
for(auto i : p[u]){
if (d[i->v] > d[u] + i->w){
if ((c[i->v]=c[u]+1) >= n) return 1;
d[i->v] = d[u] + i->w;
if (!inq[i->v]) q.push(i->v), inq[i->v] = 1;
}
}
}
return 0;
}
int main() {
#ifdef LOCAL
freopen("input", "r", stdin);
#endif
std::ios::sync_with_stdio(0); cout.tie(0);
int m; cin >> n >> m;
rep(i, 1, n) cin >> f[i];
rep(i, 1, m){
int u; cin >> u >> e[i].v >> e[i].t;
p[u].push_back(&e[i]);
}
double l = 0, r = 1000;
rep(ndacljk, 1, 20){
double mid = (l+r)/2;
rep(i, 1, m) e[i].w = mid * e[i].t - f[e[i].v];
if (spfa()){
l = mid;
} else {
r = mid;
}
}
std::cout.setf(std::ios::fixed);
cout << std::setprecision(2) << l << endl;
return 0;
}