【luogu P1073 最优贸易】题解

题目链接：https://www.luogu.org/problemnew/show/P1073

对于状态量相互影响的题目，分层图是个不错的想法。

考虑在题目中分为：

不交易：

直接从1到n出去，为0

交易：

先在某点买入，再从该点后所在路径上卖出。

买入卖出是两个操作，考虑可以分开在两张图上做，于是就有了分层图，共三张图。

我们把原图中的路径都设边权为0，表示在这条路上走对交易利润无影响，在第一张图上买入后，我们就走到下一张图，准备卖出操作。

设u—>v

所以若从u点买入，到下一条边的v，即v+n，边权为买入的花费，-val[u]。

这时我们再第二张图上的所走，就能保证是再走的路径是该点往后可以经过的路径。

这时我们再考虑转移卖出的情况。

此时已经在v+n—>w+n上

即若在v点卖出，往后可走到w点，所以是v+n到w+2n的一条边权为val[v]的路径。

图建好后，SPFA即可。

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 500010;

int n, m, val[maxn], dis[maxn];

bool vis[maxn];

struct edge{

    int from, to, next, len;

}e[maxn<<2];

int head[maxn], cnt;

queue<int> q;

void add(int u, int v, int w)

{

    e[++cnt].from = u;

    e[cnt].len = w;

    e[cnt].next = head[u];

    e[cnt].to = v;

    head[u] = cnt;

}

void SPFA()

{

    while(!q.empty())

    {

        int now = q.front(); q.pop();

        vis[now] = 0;

        for(int i = head[now]; i != -1; i = e[i].next)

        {

            if(dis[e[i].to] < dis[now] + e[i].len)

            {

                dis[e[i].to] = dis[now] + e[i].len;

                if(!vis[e[i].to])

                {

                    q.push(e[i].to);

                    vis[e[i].to] = 1;

                }

            }

        }

    }

}

int main()

{

    memset(head, -1, sizeof(head));

    scanf("%d%d",&n,&m);

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

    dis[i] = -23333333;

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

    scanf("%d",&val[i]);

    add(n, 3 * n + 1, 0);

    add(3 * n, 3 * n + 1, 0);

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

    {

        int u, v, w;

        scanf("%d%d%d",&u,&v,&w);

        if(w == 1)

        {

            add(u, v, 0);

            add(u + n, v + n, 0);

            add(u, v + n, -val[u]);

            add(u + n * 2, v + n * 2, 0);

            add(u + n, v + n * 2, val[u]);

        }

        else

        {

            add(u, v, 0);

            add(u + n, v + n, 0);

            add(u, v + n, -val[u]);

            add(u + n * 2, v + n * 2, 0);

            add(u + n, v + n * 2, val[u]);

            add(v, u, 0);

            add(v + n, u + n, 0);

            add(v, u + n, -val[v]);

            add(v + n * 2, u + n * 2, 0);

            add(v + n, u + n * 2, val[v]);

        }

    }

    q.push(1);

    dis[1] = 0;

    vis[1] = 1;

    SPFA();

    printf("%d\n",dis[3 * n + 1]);

    return 0;

}

巴特西

【luogu P1073 最优贸易】题解

最新文章

热门文章

巴特西

【luogu P1073 最优贸易】 题解

最新文章

热门文章

【luogu P1073 最优贸易】题解