[APIO2017]商旅——分数优化+floyd+SPFA判负环+二分答案

题目链接：

[APIO2017]商旅

枚举任意两个点$(s,t)$，求出在$s$买入一个物品并在$t$卖出的最大收益。

新建一条从$s$到$t$的边，边权为最大收益，长度为原图从$s$到$t$的最短路，最短路用$floyd$求即可。

对于原图的边，边权为$0$，长度为输入长度。

对于新图，需要找到一个环使得换上边的边权和比长度和最大。

显然二分答案然后分数规划，之后就变成了判断图中是否有负环，用SPFA判负环即可。

注意此题卡精，需要使用$long\ double$。

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<cstdio>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define ld long double

using namespace std;

const double eps=1e-10;

char *p1,*p2,buf[100000];

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int read() {int x=0,flag=1; char c=nc();if(c=='-'){flag=-1,c=nc();} while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return flag*x;}

int f[110][110];

int head[110];

int next[200000];

int to[200000];

int a[200000];

int b[200000];

ld v[200000];

int vis[110];

int cnt[110];

queue<int>que;

int s[110][1010];

int t[110][1010];

int tot;

int n,m,q;

int x,y,z;

ld ans;

ld dis[110];

void add(int x,int y,int w,int z)

{

    next[++tot]=head[x];

    head[x]=tot;

    to[tot]=y;

    a[tot]=w;

    b[tot]=z;

}

bool SPFA(int S)

{

    dis[S]=0;

    que.push(S);

    vis[S]=1;

    while(!que.empty())

    {

        int now=que.front();

        que.pop();

        vis[now]=0;

        for(int i=head[now];i;i=next[i])

        {

            if(dis[to[i]]>dis[now]+v[i])

            {

                dis[to[i]]=dis[now]+v[i];

                cnt[to[i]]=cnt[now]+1;

                if(cnt[to[i]]>150)

                {

                    return true;

                }

                if(!vis[to[i]])

                {

                    vis[to[i]]=1;

                    que.push(to[i]);

                }

            }

        }

    }

    return false;

}

int main()

{

    n=read();m=read();q=read();

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

    {

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

        {

            s[i][j]=read();t[i][j]=read();

        }

    }

    memset(f,0x3f,sizeof(f));

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

    {

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

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

        add(x,y,0,z);

    }

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

    {

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

        {

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

            {

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

            }

        }

    }

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

    {

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

        {

            if(f[i][j]==0x3f)continue;

            int mx=-1;

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

            {

                int num;

                if(s[i][k]==-1||t[j][k]==-1||s[i][k]>=t[j][k])continue;

                else num=t[j][k]-s[i][k];

                mx=max(mx,num);

            }

            if(mx==-1)continue;

            add(i,j,mx,f[i][j]);

        }

    }

    ld l=0,r=1e12;

    ans=-1;

    while(r-l>=eps)

    {

        ld mid=(l+r)/2;

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

        {

            v[i]=mid*b[i]-a[i];

        }

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

        {

            dis[i]=0;

            vis[i]=cnt[i]=0;

        }

        int flag=0;

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

        {

            if(dis[i]==0)

            {

                if(SPFA(i))

                {

                    l=mid;

                    ans=mid;

                    flag=1;

                    break;

                }

            }

        }

        if(!flag)

        {

            r=mid;

        }

    }

    printf("%lld",ans==-1?0ll:(ll)(ans+eps));

}