洛谷3778 [APIO2017]商旅

题目：https://www.luogu.org/problemnew/show/P3778

一看就是0/1分数规划。但不能直接套模板，因为有个商品种类的限制。

　　考虑从a买在b卖，商品种类根本没用，关注的是最大营利。于是可以考虑暴枚建一个完全图消除商品种类的影响。

　　然后就可以愉快地0/1分数规划了。

注意：1.零环也是合法的！

　　　2.！！！1点没有什么特殊的，spfa里不能只从1点走。应该把所有点都先加进队列里！图的连通性可能很差，但只要随便有个正环就行了，故应如此！

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define ll long long

using namespace std;

const int N=,M=,K=;

const ll INF=;//memset 1

int n,m,k,ct[N];

ll t[N][N],c[N][N],s[][N][K],dis[N],l,r,ans;

bool vis[N];

int rdn()

{

    int ret=,fx=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')fx=-;ch=getchar();}

    while(ch<=''&&ch>='')(ret*=)+=ch-'',ch=getchar();

    return ret*fx;

}

ll rdl()

{

    ll ret=,fx=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')fx=-;ch=getchar();}

    while(ch<=''&&ch>='')(ret*=)+=ch-'',ch=getchar();

    return ret*fx;

}

void floyd()

{

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

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

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

                t[i][j]=min(t[i][j],t[i][u]+t[u][j]);

}

ll cal(int x,int y,ll lm)

{

    return c[x][y]-t[x][y]*lm;

}

bool spfa(ll lm)

{

    queue<int> q;

    for(int i=;i<=n;i++)q.push(i),dis[i]=,vis[i]=ct[i]=;//////////////从1点不一定走到所有点(1点啥也不是)

    while(q.size())

    {

        int u=q.front();q.pop();vis[u]=;

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

            if(dis[v]<=dis[u]+cal(u,v,lm))//<=，因为零环也可以

            {

                dis[v]=dis[u]+cal(u,v,lm);

                if(!vis[v])

                {

                    q.push(v);ct[v]++;vis[v]=;//vis[v]=1!!(别忘写……)

                    if(ct[v]>n)return true;

                }

            }

    }

    return false;

}

int main()

{

    n=rdn();m=rdn();k=rdn();int x,y;ll z;

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

        for(int d=;d<=;d++)

        {

            s[d][i][u]=rdl();

            if(s[d][i][u]==-){if(!d)s[d][i][u]=INF;else s[d][i][u]=-INF;}

        }

    memset(t,,sizeof t);//c初值为0

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

    {

        x=rdn();y=rdn();z=rdl();t[x][y]=z;

    }

    floyd();

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

//        if(i!=j&&t[i][j]<INF)//写不写都行,写了更快一点//INF的t会在spfa里判掉//i与i数据应该不会给能营利的

            for(int u=;u<=k;u++)c[i][j]=max(c[i][j],s[][j][u]-s[][i][u]),r=max(r,c[i][j]);

    while(l<=r)

    {

        ll mid=((l+r)>>);

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

        else r=mid-;

    }

    printf("%lld",ans);

    return ;

}