BZOJ4898/5367 Apio2017商旅（分数规划+floyd）

时间：2024-01-18 14:57:50

　　如果要在某点买入某物品并在另一点卖出，肯定是走其间最短路径。于是预处理任意两点间的收益和最短路径，连完边二分答案判负环即可，可以全程floyd。注意inf大小。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 110

#define M 10010

#define K 1010

#define inf 1000000001

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

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

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,k,a[N][K],b[N][K],d[N][N],v[N][N],t;

ll c[N][N];

int main()

{

#ifndef ONLINE_JUDGE

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

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

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),k=read();

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

    {

        for (int j=;j<=k;j++)

        a[i][j]=read(),b[i][j]=read();

    }

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

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

        d[i][j]=inf;

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

    {

        int x=read(),y=read(),z=read();

        d[x][y]=min(d[x][y],z);

    }

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

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

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

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

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

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

            for (int x=;x<=k;x++)

            if (~b[j][x]&&~a[i][x]) v[i][j]=max(v[i][j],b[j][x]-a[i][x]);

    int l=,r=inf,ans=;

    while (l<=r)

    {

        int mid=l+r>>;

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

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

            c[i][j]=1ll*d[i][j]*mid-v[i][j];

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

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

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

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

        bool flag=;for (int i=;i<=n;i++) if (c[i][i]<=) {flag=;break;}

        if (flag) l=mid+,ans=mid;

        else r=mid-;

    }

    cout<<ans;

    return ;

}

相关文章