Sightseeing Cows

给出一张图，点数为L，边数P，并给出边的边权\(\{b_i\}\),再给处每个点的点权，求一条起点和终点相同的路径，并使其点权之和除以边权之和最大，注意，路径中点权只能被计算一次，而边权可以重复计算， (2 ≤ L ≤ 1000)， (2 ≤ P ≤ 5000)。

解

显然为分数规划问题，关键在点权与边权不对应上，于是自然的想法是点权移边权，而一条起点与终点相同的路径即一个联通分量，所以问题现在在于点权移边权后只对环成立，而不对联通分量成立，于是考虑证明联通分量对结果没有影响，于是设一个大环它的路径长\(b_1\)，点权\(a_1\),一个小环路径长\(b_2\),点权\(a_2\),设他们是套在一起的环，所以会有重叠的地方。

不难得知,大环的比率为\(\frac{a_1}{b_1}\)，小环比率\(\frac{a_2}{b_2}\)，而套在一起的环比率仍按照不去点权算为\(\frac{a_1+a_2}{b_1+b_2}\),由分数三角不等式结论，我们知道\(\frac{a_1+a_2}{b_1+b_2}\leq max(\frac{a_1}{b_1},\frac{a_2}{b_2})\)

所以我们可以知道实际上环套环，即联通分量对结果没有影响，于是移点下边，接下来照着最优比率环的基本套路即可，但是注意此处要算出一个具体的比较大的ans很难做到，于是迭代就不能使用了，但是你的聪明才智或许能想到一种好的解决办法。

参考代码：

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#define il inline

#define ri register

#define exact 0.000001

using namespace std;

struct point{

    int next,to,a,b;

    double c;

}ar[5001];int at;

bool is[1001];

double dis[10001];

int f[1001],head[1001],n,

    t1[4000001],tot[1001];

il bool check(double);

il double dfs(double,double);

il void link(int,int,int,int),read(int&);

int main(){

    int m,i,j,k;

    read(n),read(m);

    for(i=1;i<=n;++i)read(f[i]);

    while(m--)read(i),read(j),read(k),

                  link(i,j,f[j],k);

    printf("%.2lf",dfs(0,100));

    return 0;

}

il bool check(double x){

    int i,h(0),t(0);

    memset(is,0,sizeof(is)),memset(tot,0,sizeof(tot)),

        memset(dis,0,sizeof(dis));

    for(i=1;i<=n;++i)t1[++t]=i;

    for(i=1;i<=at;++i)

        ar[i].c=ar[i].b*x-ar[i].a;

    while(h<t){

        ++h,is[t1[h]]|=true;

        for(i=head[t1[h]];i;i=ar[i].next)

            if(ar[i].c+dis[t1[h]]<dis[ar[i].to]){

                dis[ar[i].to]=ar[i].c+dis[t1[h]];

                if(is[ar[i].to]){

                    t1[++t]=ar[i].to,is[ar[i].to]&=false;

                    if(++tot[ar[i].to]>=n)return true;

                }

            }

    }return false;

}

il double dfs(double l,double r){

    double mid;

    while(r-l>exact){

        mid=(l+r)/2;

        if(check(mid))l=mid+exact;

        else r=mid-exact;

    }return (l+r)/2;

}

il void read(int &x){

    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

}

il void link(int x,int y,int a,int b){

    ar[++at].a=a,ar[at].b=b,ar[at].to=y;

    ar[at].next=head[x],head[x]=at;

}

巴特西

Sightseeing Cows

解

最新文章

热门文章