[BZOJ4898] [Apio2017]商旅

[传送门](JudgeOnline/upload/201806/merchant (zh_CN).pdf)

试题分析

考虑两个点之间的路径，显然如果交易的话肯定选\(S_{t,i}-B_{s,i}\)最大的。

那么我们可以先用\(Cost\)把两个点的最大收益预处理出来，然后找正环就可以了。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<cmath>

#include<algorithm>

using namespace std;

#define LL long long

inline int read(){

    int x=0,f=1; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

    return x*f;

}

const double INF = 1e12;

const int MAXN = 100010;

const double eps = 1e-6;

int N,M,K;

double B[101][1001],S[101][1001];

double E[101][101],Fd[101][101],Cost[101][101];

double dis[MAXN+1]; bool inq[MAXN+1];

int cnt[MAXN+1];

inline bool check(double r){

    queue<int> que;

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

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

            if(i!=j&&Cost[i][j]>=0) E[i][j]=Cost[i][j]-r*Fd[i][j];

            else E[i][j]=-INF;

        } dis[i]=0.0; que.push(i); inq[i]=true;

        //cout<<endl;

    } //memset(inq,false,sizeof(inq));

    memset(cnt,0,sizeof(cnt));

    while(!que.empty()){

        int k=que.front(); inq[k]=false; que.pop();

        for(int v=1;v<=N;v++){

            if(dis[v]<dis[k]+E[k][v]){

                dis[v]=dis[k]+E[k][v];

                if(!inq[v]){

                    inq[v]=true; ++cnt[v];

                    que.push(v); if(cnt[v]>N) return true;

                }

            }

        }

    } return false;

}

int main(){

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

    //freopen(".out","w",stdout);

    N=read(),M=read(),K=read();

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

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

            B[i][j]=read();

            S[i][j]=read();

        }

    }

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

        for(int j=1;j<=N;j++) E[i][j]=INF;

    }

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

        int u=read(),v=read(); double w=read();

        E[u][v]=min(w,E[u][v]);

    } double Mx=0;

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

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

            if(j!=i){

                double ret=0;

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

                    if(S[i][k]!=-1&&B[j][k]!=-1)

                        ret=max(ret,S[i][k]-B[j][k]);

                Cost[j][i]=ret; Mx=max(Mx,ret);

            } else Cost[j][i]=-INF;

            Fd[i][j]=E[i][j];

        }

    }

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

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

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

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

    }

    double l=0,r=Mx,ans=0;

    while(r-l>=eps){

        double mid=(l+r)/2.0;

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

        else r=mid;

    } if((int)floor(ans)==0&&(int)(floor(ans+(1e-6)))==1) puts("0");

    else printf("%d\n",(int)(floor(ans+(1e-6))));

    return 0;

}

巴特西

[BZOJ4898] [Apio2017]商旅

[BZOJ4898] [Apio2017]商旅

试题分析

最新文章

热门文章