传送门:[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的边。

将图建好之后,采用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; }
Comments NOTHING