[NOIP2009]最优贸易(分层图论 + SPFA最长路)

发布于 2022-03-15  1293 次阅读


传送门:[NOIP2009]最优贸易 (nowcoder.com)

传送门2:P1073 [NOIP2009 提高组] 最优贸易 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题思路比较多,有分层图论,还可以用Tarjan缩点 + DP,由于俺的水平不够,所以用分层图论吧。

之前也写过一篇分层图论的文章《[JLOI2011]飞行路线(dijkstra分层最短路) – ErikTse Runtime》。

思路分析:

注意题目中说到“一定从1节点开始,N节点离开”。并且每个点的状态有三个,分别是:

  • 没买入
  • 买入没卖出
  • 卖出了

那么考虑将图分成三层,最上层(第一层)代表没买入的点,中间层(第二层)表示买入没卖出的点,最下层(第三层)表示卖出了的点。

每一层分别有N个,可以用一维数组表示。[1,N]表示第一层,[N + 1,N * 2]表示第二层,[N * 2 + 1,N * 3]表示第三层。

不难发现,每一层之间可以自由移动(权值为0),因为同一层之间移动不会发生状态变化,所以权值为0

边,只能在同一层中或从上层指向下层,因为不可能从买入没卖出的状态进入没买入的状态。

商人只进行一次交易,起点为1,终点为最下层的N,也就是数组中的3 * N,注意商人可能没进行交易,所以要加一条从N到3 * N权值为0的边

图片来自洛谷P1073题解

将图建好之后,采用SPFA求一次最长路,因为dijkstra不能求最长路,所以采用已死的SPFA(其实SPFA的效率比Bellman-Ford还好,但是在竞赛界风评不好)

SPFA的算法具体过程:

  • 创建队列queue<int> q
  • 创建inq[]数组表示某个点是否在队列中,inq数值随着push和pop变化。
  • int d[]表示某个点到起点的最大距离,初始化为-inf
  • 当w + d[x] > d[nx]时,更新nx的值,如果nx不在队列中就入队,已在就不管

代码

/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <bitset>
#include <utility>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define sc scanf
#define pb push_back
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
	int s = 0,w = 1;char c = gc();
	while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
	while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
	return s * w;
}
/*--------全局变量--------*/
typedef pair<int, int> PII;
const int maxn = 1e5 + 9,inf = 1e9;
int N, M;
int val[maxn];
struct Edge{int x, w;};
vector<Edge> g[maxn * 3];//分三层 
int d[maxn * 3];
/*--------自定义函数-------*/

void spfa(int s)
{
	for(int i = 1;i <= N * 3; ++ i)d[i] = -inf;
	bitset<maxn * 3> inq;//inq表示在队列中 
	d[s] = 0;
	queue<int> q;inq[s] = 1;q.push(s);
	while(!q.empty())
	{
		int x = q.front();inq[x] = 0;q.pop();
		for(auto [nx, nw] : g[x])
		{
			if(d[x] + nw > d[nx])
			{
				d[nx] = d[x] + nw;
				if(!inq[nx]){inq[nx] = 1;q.push(nx);}
			}
		}
	}
}

signed main()
{
//	freopen("in.txt","r",stdin);
	cin >> N >> M;
	for(int i = 1;i <= N; ++ i)val[i] = readInt();
	int T = 3 * N;
	while(M --)
	{
		int x = readInt(), y = readInt(), op = readInt();
		g[x].pb({y, 0});
		g[x].pb({N + x, -val[x]});
		g[N + x].pb({N + y, 0});
		g[N + x].pb({N * 2 + x, val[x]});
		g[N * 2 + x].pb({N * 2 + y, 0});
		if(op == 2)
		{
			g[y].pb({x, 0});
			g[y].pb({N + y, -val[y]});
			g[N + y].pb({N + x, 0});
			g[N + y].pb({N * 2 + y, val[x]});
			g[N * 2 + y].pb({N * 2 + x, 0});
		}
	}
	g[N].pb({T, 0});
    spfa(1);
    pr("%lld\n", d[T]);
	return 0;
}