嘟嘟嘟

这题好像属于01分数规划问题，叫什么最优比率生成环。

题目概括一下，就是求一个环，满足∑v[i] / ∑c[i]最大。

我们可以堆上面的式子变个型：令 x = ∑v[i] / ∑c[i],则x * ∑c[i] = v[i] => ∑x * c[i] - v[i] = 0。于是对于任何能取到的x',满足∑x * c[i] - v[i] <= 0；对于不能取到的x', ∑x * c[i] - v[i] > 0。

于可以实数二分答案，用spfa判断负环。

然后实数二分又RE了……调了好就还是看了题解。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 1e3 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << ) + (ans << ) + ch - '', ch = getchar(); if(las == '-') ans = -ans; return ans; } inline void write(ll x) { if(x < ) putchar('-'), x = -x; if(x >= ) write(x / );
putchar(x % + '');
}

int n, m, val[maxn];
vector v[maxn], c[maxn];

bool in[maxn];
db dis[maxn];
int cnt[maxn];
bool judge(db x)
{
Mem(in, ); Mem(cnt, ); Mem(dis, );
queue q;
for(int i = ; i <= n; ++i) q.push(i); while(!q.empty()) { int now = q.front(); q.pop(); in[now] = ; for(int i = ; i < (int)v[now].size(); ++i) { if(dis[v[now][i]] > x * c[now][i] - val[v[now][i]] + dis[now])
{
dis[v[now][i]] = x * c[now][i] - val[v[now][i]] + dis[now];
if(!in[v[now][i]])
{
if(++cnt[v[now][i]] == n - ) return ;
q.push(v[now][i]);
}
}
}
}
return ;
}

int main()
{
n = read(); m = read();
for(int i = ; i <= n; ++i) val[i] = read(); for(int i = ; i <= m; ++i) { int x = read(), y = read(), co = read(); v[x].push_back(y); c[x].push_back(co); } db L = , R = 1e6; while(R - L > eps)
{
db mid = (L + R) / ;
if(judge(mid)) L = mid;
else R = mid;
}
if(L < eps) write(), enter;
else printf("%.2lf\n", L);
return ;
}