【bzoj4898】商旅

Portal -->bzoj4898

Solution

　　这题的话。。首先答案的形式应该是\(01\)分数规划了

　　然后比较关键的一步在于，我们需要简化一下交易的过程

　　具体一点就是，我们将中间经过的不交易的点和路径全部”合并“起来，只考虑买入物品和卖出物品的两个点

　　首先看一下这两个点之间的路程应该怎么走

　　因为路程长度是做分母的那个，所以我们肯定希望在到达同一个点的情况下走最短路，那所以这两个点一旦确定下来了，路程也就确定下来了

　　两两之间最短路的求解因为\(N\)比较小所以可以直接用floyd解决

　　然后接下来就是交易的物品我们要选择哪一个

　　很明显是选盈利最大的那个，大力贪心就好了ovo

　　所以总的来说，如果确定了进行买卖的两个点，我们走的路程一定是最短路，买卖的一定是这两个点能够交易的所有物品中，盈利最大的那个

　　记两点间最短路为\(w_{i,j}\)，最优的盈利为\(val_{i,j}\)，那么套用分数规划的套路（Portal -->【learning】），我们需要快速求出一个环的：

\[max(\sum val_{i,j}-\lambda' \sum w_{i,j})
\]

　　与\(0\)的大小关系

　　那么这个其实就直接用spfa判断是否有正环就好了

　　自己跳进去的坑：

　　　　额。。注意到这里题目说的是**利润/路径长度（向下取整） **的最大值。。

　　　　所以！在二分答案的时候！\(l\)和\(r\)和\(mid\)用int就好了！！ QWQ

　　　　以及\(K\)的范围是\(1000\)而不是\(100\)。。。

　　代码大概长这个样子

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N=110,M=9910,inf=2147483647;

const double eps=1e-8;

struct xxx{

    int y,x,nxt;

    double w;

}a[N*N*2];

struct Data{

    int y,x;

    int w;

}rec[N*N*2];

queue<int> q;

int h[N],cnt[N],buy[N][1010],sell[N][1010],w[N][N];

double val[N];

bool vis[N];

int n,m,K,tot,rec_cnt;

void add(int x,int y,double val);

bool spfa();

void build(double mid);

bool check(double mid);

void prework();

void floyd();

void solve();

int main(){

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

#endif

    scanf("%d%d%d",&n,&m,&K);

    for (int i=1;i<=n;++i)

        for (int j=1;j<=K;++j)

            scanf("%d%d",&buy[i][j],&sell[i][j]);

    int x,y,w1;

    rec_cnt=0;

    for (int i=1;i<=n;++i)

        for (int j=1;j<=n;++j)

            w[i][j]=inf;

    for (int i=1;i<=m;++i){

        scanf("%d%d%d",&x,&y,&w1);

        rec[++rec_cnt].x=x; rec[rec_cnt].y=y; rec[rec_cnt].w=0;

        w[x][y]=min(w[x][y],w1);

    }

    prework();

    solve();

}

void add(int x,int y,double val){

    //printf("%d %d %.3lf\n",x,y,val);

    a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot; a[tot].w=val;

}

bool spfa(){

    while (!q.empty()) q.pop();

    int u,v;

    for (int i=1;i<=n;++i) vis[i]=true,q.push(i),cnt[i]=0,val[i]=0;

    while (!q.empty()){

        v=q.front(); q.pop();

        for (int i=h[v];i!=-1;i=a[i].nxt){

            u=a[i].y;

            if (val[u]<=val[v]+a[i].w){

                val[u]=val[v]+a[i].w;

                if (!vis[u]){

                    q.push(u),vis[u]=true,++cnt[u];

                    if (cnt[u]>n) return true;

                }

            }

        }

        vis[v]=false;

    }

    return false;

}

bool check(double mid){

    build(mid);

    return spfa();

}

void build(double mid){

    tot=0;

    for (int i=1;i<=n;++i) h[i]=-1;

    for (int i=1;i<=rec_cnt;++i)

        add(rec[i].x,rec[i].y,1.0*rec[i].w-mid*w[rec[i].x][rec[i].y]);

}

void floyd(){

    for (int k=1;k<=n;++k)

        for (int i=1;i<=n;++i){

            if (w[i][k]==inf) continue;

            for (int j=1;j<=n;++j)

                if (w[k][j]!=inf)

                    w[i][j]=min(w[i][j],w[i][k]+w[k][j]);

        }

}

void prework(){

    floyd();

    int mx,tmp;

    for (int i=1;i<=n;++i)

        for (int j=1;j<=n;++j){

            if (w[i][j]==inf) continue;

            mx=0;

            for (int k=1;k<=K;++k)

                if (buy[i][k]!=-1&&sell[j][k]!=-1){

                    if (sell[j][k]-buy[i][k]>mx) tmp=k;

                    mx=max(mx,sell[j][k]-buy[i][k]);

                }

            if (mx)

                rec[++rec_cnt].x=i,rec[rec_cnt].y=j,rec[rec_cnt].w=mx;

        }

}

void solve(){

    int l=0,r=1e9,mid,ans;

    while (l<=r){

        mid=(l+r)>>1;

        if (check(mid)) ans=mid,l=mid+1;

        else r=mid-1;

    }

    printf("%d\n",ans);

}

巴特西

【bzoj4898】商旅

Solution

最新文章

热门文章