这题好像属于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了……调了好就还是看了题解。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std;12 #define enter puts("")13 #define space putchar(' ')14 #define Mem(a, x) memset(a, x, sizeof(a))15 #define rg register16 typedef long long ll;17 typedef double db;18 const int INF = 0x3f3f3f3f;19 const db eps = 1e-4;20 const int maxn = 1e3 + 5;21 inline ll read()22 {23 ll ans = 0;24 char ch = getchar(), las = ' ';25 while(!isdigit(ch)) las = ch, ch = getchar();26 while(isdigit(ch)) ans = (ans << 3) + (ans << 1) + ch - '0', ch = getchar();27 if(las == '-') ans = -ans;28 return ans;29 }30 inline void write(ll x)31 {32 if(x < 0) putchar('-'), x = -x;33 if(x >= 10) write(x / 10);34 putchar(x % 10 + '0');35 }36 37 int n, m, val[maxn];38 vector v[maxn], c[maxn];39 40 bool in[maxn];41 db dis[maxn];42 int cnt[maxn];43 bool judge(db x)44 {45 Mem(in, 0); Mem(cnt, 0); Mem(dis, 0);46 queue q;47 for(int i = 1; i <= n; ++i) q.push(i);48 while(!q.empty())49 {50 int now = q.front(); q.pop(); in[now] = 0;51 for(int i = 0; i < (int)v[now].size(); ++i)52 {53 if(dis[v[now][i]] > x * c[now][i] - val[v[now][i]] + dis[now])54 {55 dis[v[now][i]] = x * c[now][i] - val[v[now][i]] + dis[now];56 if(!in[v[now][i]])57 {58 if(++cnt[v[now][i]] == n - 1) return 1;59 q.push(v[now][i]);60 }61 }62 }63 }64 return 0;65 }66 67 int main()68 {69 n = read(); m = read();70 for(int i = 1; i <= n; ++i) val[i] = read();71 for(int i = 1; i <= m; ++i)72 {73 int x = read(), y = read(), co = read();74 v[x].push_back(y); c[x].push_back(co);75 }76 db L = 0, R = 1e6;77 while(R - L > eps)78 {79 db mid = (L + R) / 2;80 if(judge(mid)) L = mid;81 else R = mid;82 }83 if(L < eps) write(0), enter;84 else printf("%.2lf\n", L);85 return 0;86 }