题解 P2868 【[USACO07DEC]观光奶牛Sightseeing Cows】

· · 题解

题解里似乎都没有提到这么一种情况，如果环里经过一个点两次（去一次，回来一次），点的fi只会被计算一次，但是如果按照题解里的算法的话，这个点的fi会被计算两次。

如果一个点被计算两次的话，分子上的东西就比分母上的东西少，以下推导都没法进行。

（这个bug让我在模拟赛里面不敢写0/1规划算法，最后此题0分QwQ

现在就要证明，如果环上的比率最优，则必然不会有一个点被经过两次。

首先，如果一个环经过一个点两次，则必然可以通过那个点（设为P_x）分成两个没有相交点的环。方便起见，设两个环的快乐值总和分别为F_1和F_2，用时总和分别为T_1和T_2，x点的快乐值为F_x

我们的目标就是证明：

\frac{F_1}{T_1}\geq\frac{F_1+F_2-F_x}{T_1+T_2}\space\space\space or\space\space\space\frac{F_2}{T_2}\geq\frac{F_1+F_2-F_x}{T_1+T_2}

由于右式含有T1+T2作为分母，因此就可以考虑将两环求平均数。即，只需要证明：

\frac{F_1}{2\times T_1}+\frac{F_2}{2\times T_2} \geq \frac{F_1+F_2-F_x}{T_1+T_2} \frac{F_1T_2+F_2T_1}{2(T_1+T_2)}\geq\frac{F_1+F_2-F_x}{T_1+T_2}

因为我们分的两个都是环，至少要经过两条边，同时题目保证T_i\geq1，所以可以得出T_1\geq2且T_2\geq2。

因此，可得：

\frac{F_1T_2+F_2T_1}{2(T_1+T_2)}\geq\frac{F_1+F_2}{T_1+T_2}> \frac{F_1+F_2-F_x}{T_1+T_2}

Q.E.D.

因此，我们可以得出，该算法只适用于T_i\geq1的题目，如果允许边权等于0或者为小于1的小数的话，就得另找算法。

（很有可能是爆搜了QwQ）

其他部分题解的各位神仙已经讲得很清楚了，为了内容的完整性，还是写完吧QwQ。

首先，原题可以转化为，求一个环，使得\frac{\sum F_i}{\sum T_i}最小。由于上面花了几行证明上下齐项，可以应用0/1分数规划。

对于0/1分数规划，考虑二分。二分可将一个最优化问题转化为一个判定问题。如果二分出来的mid为L，则问题就转化为是否存在一个\frac{\sum F_i}{\sum T_i}> L

分数乘过去（保证T_i>0），减回来，得：

\sum(F_i-L\times T_i) > 0

由于左式不好搞，考虑变换。如果将左式乘以-1，原式变为：

\sum(L\times T_i-F_i)>0

既然所有边成一个环，那不就是一个负环的方程嘛？？

于是算法就出来了，先二分答案，然后对于一个mid，将边权变为边权乘mid再减去一个端点的F[i]（随便入端点还是出端点，反正是个环），最后stacked spfa找负环判定。

附AC代码：

#include <stack>
#include <cmath>
#include <cstdio>
using namespace std;

inline double lfabs(double x)
{
    return x<0?-x:x;
}

int beg[1005];
int ed[5005];
int nxt[5005];
int len[5005];
int top;

void addedge(int a,int b,int c)
{
    ++top;
    ed[top] = b;
    len[top] = c;
    nxt[top] = beg[a];
    beg[a] = top;
}
int n;
int fi[5005];
int inq[5005];
int inqn[5005];
double dist[5005];

bool spfa(int s,double delta)
{
    dist[s] = 0;
    inq[s] = 0;

    stack<int> stk;
    stk.push(s);

    while(!stk.empty())
    {
        int th = stk.top();
        stk.pop();
        inq[th] = 0;

        for(int p=beg[th]; p; p=nxt[p])
        {
            if(dist[th] + (delta*len[p]-fi[th]) < dist[ed[p]])
            {
                dist[ed[p]] = dist[th] + (delta*len[p]-fi[th]);

                if(!inq[ed[p]])
                {
                    stk.push(ed[p]);
                    ++inqn[ed[p]];
                    inq[ed[p]] = 1;

                    if(inqn[ed[p]] > n+10)
                    {
                        return true;
                    }
                }
            }
        }
    }

    return false;
}

int main()
{
    int p;
    scanf("%d%d",&n,&p);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",fi+i);
    }
    for(int i=1; i<=p; ++i)
    {
        int a,b,t;
        scanf("%d%d%d",&a,&b,&t);
        addedge(a,b,t);
    }

    double l = 0;
    double r = 1005;
    while(lfabs(r-l) >= 0.0001)
    {
        double mid = (l+r)/2;

        for(int i=1; i<=n; ++i)
        {
            dist[i] = 99999999;
            inq[i] = inqn[i] = 0;
        }

        for(int i=1; i<=n; ++i)
        {
            if(!inqn[i])
            {
                if(spfa(i,mid))
                {
                    l = mid;
                    goto die;
                }
            }
        }

        r = mid;

        die:;
    }

    printf("%.2lf",l+0.00005);
}