题解 P1073 【最优贸易】

万弘 · 2019-01-30 22:30:07 · 题解

分层图入门

在一些图论题中,可能会有多个状态,如此题,此时分层图很有效

分层图,就是将同一个图复制多次,用一些边将这些图连接，再把这些图看为一个整体，在这个整体上跑一些算法。

此题就可以这样做：

1.建立原图（边权为0）同时在复制的图（复制两个，一个称为“买图”，一个称为“卖图”）中也这样做；
2.将原图与“买图”的对应点连接，边权为买入价（正数数）；
3.将“买图”与“卖图”的对应点连接，边权为卖出价（负数）；
4.从原图中的点1开始跑最短路，到“卖图”的点n的距离的相反数即为答案

由于有负边权，所以必须用SPFA

还是有一定思维难度的，复杂度O(m)-O(nm)（SPFA就是这样..不过亲测可过）

//by wh
//time O(km)~O(nm)
#include<iostream>
#include<cstdio>
typedef long long ll;
#define maxn 400004
#define maxm 2000004
ll n,m;
struct Edge//邻接表存图
{
    ll v,w,nxt;
}e[maxm];
ll cnt=0,last[maxn];
void adde(ll u,ll v)//在三个图中增加u->v的边，边权为0
{
    ++cnt;
    e[cnt].v=v;e[cnt].w=0;
    e[cnt].nxt=last[u];last[u]=cnt;
    ++cnt;
    e[cnt].v=(v+n);e[cnt].w=0;
    e[cnt].nxt=last[u+n];last[u+n]=cnt;
    ++cnt;
    e[cnt].v=(v+n*2);e[cnt].w=0;
    e[cnt].nxt=last[u+n*2];last[u+n*2]=cnt;
}

ll dis[maxn];//到各个点的最短距离
bool inq[maxn];
struct que//queue 手打队列
{
    ll a[maxn],h,t;
    void start()
    {
        h=t=1;
    }
    void push(ll x)
    {
        a[t++]=x;
        if(t>maxn)t=1;
    }
    void pop()
    {
        ++h;
        if(h>maxn)h=1;
    }
    ll front()
    {
        return a[h];
    }
    bool empty()
    {
        return h==t;
    }
}q;
void SPFA()
{
    for(ll i=1;i<=n*3;++i)dis[i]=1ll<<60;
    dis[1]=0;
    q.start();
    q.push(1);inq[1]=1;
    ll u,v,w;
    while(!q.empty())
    {
        u=q.front();
        q.pop();inq[u]=0;
        for(ll i=last[u];i;i=e[i].nxt)
        {
            v=e[i].v,w=e[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!inq[v])
                {
                    q.push(v);inq[v]=1;
                }
            }
        }
    }
}
int main()
{
    scanf("%lld%lld",&n,&m);
    ll t,u,v;
    for(ll i=1;i<=n;++i)
    {
        scanf("%lld",&t);
        ++cnt;//跨图连边，即步骤2&3
        e[cnt].v=(i+n);e[cnt].w=t;
        e[cnt].nxt=last[i];last[i]=cnt;
        ++cnt;
        e[cnt].v=(i+n*2);e[cnt].w=-t;
        e[cnt].nxt=last[i+n];last[i+n]=cnt;
    }
    for(ll i=1;i<=m;++i)
    {
        scanf("%lld%lld%lld",&u,&v,&t);
        adde(u,v);
        if(t==2)adde(v,u);
    }
    SPFA();
    printf("%lld",-dis[n*3]);
    return 0;
}

比较奇妙的