[USACO07DEC]Sightseeing Cows

嘟嘟嘟

这题好像属于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<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<cstdlib>

 #include<cctype>

 #include<stack>

 #include<queue>

 #include<vector>

 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<int> v[maxn], c[maxn];

 bool in[maxn];

 db dis[maxn];

 int cnt[maxn];

 bool judge(db x)

 {

   Mem(in, ); Mem(cnt, ); Mem(dis, );

   queue<int> 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 ;

 }