题目内容

P1073

大意:一个商人在一个国家(n个城市m条路)游玩,每到一个城市可以选择买入或者卖出物品,贸易只进行一次,从1出发,到n结束,求最大获利

解题思路

嗯,遇到这种贸易问题,可以抽象成图来看。

商人完整的贸易过程分为三个部分:出发到买入,买入到卖出,卖出到结束

可以使用分层图的思想,将整张图复制为三份,然后在第一层到第二层每个点之间连边,边权为该点的物价,在第二层到第三层之间每个点连边,边权为物价的相反数。然后每一层中间城市的道路边权都为0,因为在城市间移动不需要费用。

对于商人的移动,层内的对应的是正常移动,跨层的是买卖操作,求出从第一层的1号节点到第三层的n节点的最短路再取相反数即可。

代码细节

首先,由于负权边的存在,最短路的算法要使用SPFA,实现的细节不再赘述。

其次,分层图的表示,使用的是1\~n号代表第一层,n+1\~2n号代表第二层,2n+1~3n号代表第三层。对于每一个节点编号为i,权值为c_i的节点,需要添加边(i,n+i)=c_i(n+i,2n+i)=-c_i

至于城市间道路的添加,需要在三层图上都分别添加,注意双向边的存在。

多层图的节点切记不是2*n或3*n,我第一次打的时候就因为这个spfa陷入了死循环

注意如果商人不能获得优惠的话就不进行贸易输出0

代码

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn=1e5+5;

struct edge
{
    int from,to,dist;
    edge(){}
    edge(int u,int v,int w)
    {
        from=u,to=v,dist=w;
    }
};

vector<edge> g[maxn*3];//开空间的时候maxn要乘上3
queue<int> q;
bool inq[maxn*3];
int d[maxn*3];
int n,m;

void ins(int u,int v,int w)
{
    g[u].push_back(edge(u,v,w));
    return;
}

int spfa()
{
    memset(d,0x3f3f3f3f,sizeof(d));
    q.push(1);
    inq[1]=true;
    d[1]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        inq[now]=false;
        for(auto &e:g[now])
        {
            int to=e.to, dist=e.dist;
            if(d[now]+dist<d[to])
            {
                d[to]=d[now]+e.dist;
                if(!inq[to])
                {
                    inq[to]=true;
                    q.push(to);
                }
            }
        }
    }
    return d[n+(n<<1)];//返回值是到终点的最小值
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d",&k);
        ins(i,i+n,k);//记得加边
        ins(i+n,i+(n<<1),-k);//第二,三层之间边权是负的
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        ins(u,v,0);//三层边都要加上
        ins(u+n,v+n,0);
        ins(u+(n<<1),v+(n<<1),0);
        if(w==2)//如果是双向边的话也要加上
        {
            ins(v,u,0);
            ins(v+n,u+n,0);
            ins(v+(n<<1),u+(n<<1),0);
        }
    }
    int ans=spfa();
    //这里如果ans小于0,说明能获利,否则不能获利就不进行贸易,输出0
    printf("%d\n",ans<0?-ans:0);
    return 0;
}
最后修改日期:2020年2月3日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。