题目描述
C 国有 \(n\) 个大城市和 \(m\) 条道路，每条道路连接这 \(n\) 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 \(m\) 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 \(1\) 条。
C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 \(1~n\) 个城市的标号从 ，阿龙决定从 \(1\) 号城市出发，并最终在 \(n\) 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 个城市。
阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设 C 国有 \(5\) 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设 \(1\)~\(n\) 号城市的水晶球价格分别为 \(4, 3, 6, 5, 1\) 。
阿龙可以选择如下一条线路：\(1 - 2 - 3 - 5\)，并在 \(2\) 号城市以 \(3\) 的价格买入水晶球，在 \(3\) 号城市以 \(5\) 的价格卖出水晶球，赚取的旅费数为 \(2\) 。
阿龙也可以选择如下一条线路 \(1 - 4 - 5 - 4 - 5\) ，并在第 \(1\) 次到达 \(5\) 号城市时以 \(1\) 的价格买入水晶球，在第 \(2\) 次到达 \(4\) 号城市时以 \(6\) 的价格卖出水晶球，赚取的旅费数为 \(5\) 。
现在给出 \(n\) 个城市的水晶球价格， \(m\) 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
输入格式
第一行包含 \(2\) 个正整数 \(n\) 和 \(m\)，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 \(n\) 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 \(n\) 个城市的商品价格。
接下来 \(m\) 行，每行有$ 3 $个正整数 \(x,y,z\)，每两个整数之间用一个空格隔开。如果 \(z=1\)，表示这条道路是城市 \(x\) 到城市 \(y\) 之间的单向道路；如果 \(z=2\)，表示这条道路为城市 \(x\) 和城市 \(y\) 之间的双向道路。
输出格式
一个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出 \(0\)。
样例输出
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
样例输出
5
数据范围与提示
输入数据保证 \(1\) 号城市可以到达$ n $号城市。
对于 \(10\%\) 的数据，\(1≤n≤6\)。
对于 \(30\%\) 的数据，\(1≤n≤100\)。
对于 \(50\%\) 的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。
对于 \(100\%\) 的数据，\(1≤n≤100000\)，\(1≤m≤500000\)，\(1≤x\)，\(y≤n\)，\(1≤z≤2\)，\(1≤\)各城市
水晶球价格 \(≤100\)。
0x01 前置芝士
又来水题解了呢。
比较老的一道真题了，之前也做过一次，算是旧题重做吧。
所用知识点：dp，拓扑排序，spfa，分层图思想，tarjan（？
0x02 关于部分分
最近的联赛让我有了看部分分的习惯。
首先这道题我们可以抽象成这样一个命题：
一张图中，任意一点 \(x\)， 求从 \(1\) 走到 \(n\) 并且过点 \(x\) 的路径上，点 \(x\) 前面的最小点权，与点 \(x\) 后面的最大点权的差的最大值。（简单贪心可证。我们需要让进价少，售价大。
也就是说对于一个点 \(x\)，我们只需要算出 \(ma[x]\) 与 \(mi[x]\) 即可，\(ma[x]\) 表示点 \(x\) 到 \(n\) 的所有路径中的最大点权，\(mi[x]\) 表示点 \(1\) 到 \(x\) 的所有路径的最小点权。
又因为这道题保证有 \(50pt\) 无环。于是直接两次拓扑，一次正一次反即可。
#include <cstdio>
#include <queue>
using namespace std;
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
const int MAXN = 1e5 + 5;
const int MAXE = 5e5 * 2 + 5;
int lenf = 0, headf[MAXE];
int lenb = 0, headb[MAXE];
struct edge {
int to, next;
edge() {}
edge(int To, int Next) {
to = To;
next = Next;
}
} ef[MAXE], eb[MAXN];
void Add_Edge_front(int u, int v) {
ef[++lenf].to = v;
ef[lenf].next = headf[u];
headf[u] = lenf;
}
void Add_Edge_back(int u, int v) {
eb[++lenb].to = v;
eb[lenb].next = headb[u];
headb[u] = lenb;
}
int w[MAXN];
bool visf[MAXN], visb[MAXN];
int ma[MAXN], mi[MAXN], inf[MAXN], inb[MAXN];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
mi[i] = ma[i] = w[i];
}
for (int i = 1; i <= m; i++) {
int u, v, flag;
scanf("%d %d %d", &u, &v, &flag);
Add_Edge_front(u, v);
Add_Edge_back(v, u);
inf[v]++;
inb[u]++;
if (flag == 2) {
Add_Edge_front(v, u);
Add_Edge_back(u, v);
inf[u]++;
inb[v]++;
}
}
queue<int> qf;
qf.push(1);
visf[1] = true;
while (!qf.empty()) {
int u = qf.front();
qf.pop();
for (int i = headf[u]; i; i = ef[i].next) {
int v = ef[i].to;
inf[v]--;
visf[u] = true;
mi[v] = Min(mi[v], w[u]);
if (inf[v] == 0)
qf.push(v);
}
}
queue<int> qb;
qb.push(n);
visb[n] = true;
while (!qb.empty()) {
int u = qb.front();
qb.pop();
for (int i = headb[u]; i; i = eb[i].next) {
int v = eb[i].to;
inb[v]--;
ma[v] = Max(ma[v], w[u]);
visb[v] = true;
if (inb[v] == 0)
qb.push(v);
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (visb[i] && visf[i])
ans = Max(ans, ma[i] - mi[i]);
printf("%d\n", ans);
return 0;
}
0x03 正解
part1: Tarjan + Topology_Sort
这方面的正解主要是优化之前的拓扑解法。
如何在有环图上跑拓扑？好像不会。但我们会把有环变无环对吧！
于是可以考虑在上述算法前事先 Tarjan 缩点。
当然，本人没调出来。
part2: 类 spfa 解法
事实证明，spfa 可以在有环图上完成部分拓扑排序的工作。
就像 spfa 可以在有环图上完成部分 dijkstra 的工作一样。
对于 spfa， 你会发现，它本质上也是一种根据一定遍历顺序完成图论问题的算法。
也就是说它也可以达到将图拉成类似一条链的结构方便去线性 dp。
具体的，不难看出当且仅当一个点的 \(ma[]\) 或者 \(mi[]\) 发生改变，它才会对后面遍历的点产生影响。
那我们就在每次发生更新之后，让当前结点重新入队即可。
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
inline int Max(int x, int y) {return x > y ? x : y;}
inline int Min(int x, int y) {return x < y ? x : y;}
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
vector<int> mp1[MAXN], mp2[MAXN];
int w[MAXN];
int mi[MAXN], ma[MAXN];
int main() {
int n, m;
scanf ("%d %d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf ("%d", &w[i]);
mi[i] = INF;
}
for(int i = 1; i <= m; i++) {
int u, v, flag;
scanf ("%d %d %d", &u, &v, &flag);
mp1[u].push_back(v);
mp2[v].push_back(u);
if(flag == 2) {
mp1[v].push_back(u);
mp2[u].push_back(v);
}
}
queue<int> q;
q.push(1);
while(!q.empty()) {
int u = q.front();
q.pop();
mi[u] = Min(w[u], mi[u]);
int len = mp1[u].size();
for(int i = 0; i < len; i++) {
int v = mp1[u][i];
if(w[u] < mi[v]) {
mi[v] = w[u];
q.push(v);
}
}
}
q.push(n);
while(!q.empty()) {
int u = q.front();
q.pop();
ma[u] = Max(w[u], ma[u]);
int len = mp2[u].size();
for(int i = 0; i < len; i++) {
int v = mp2[u][i];
if(w[u] > ma[v]) {
ma[v] = w[u];
q.push(v);
}
}
}
int ans = 0;
// for(int i = 1; i <= n; i++)
// printf("ma[%d] = %d, mi[%d] = %d\n", i, ma[i], i, mi[i]);
for(int i = 1; i <= n; i++)
ans = Max(ans, ma[i] - mi[i]);
printf("%d\n", ans);
return 0;
}
part3: 分层图。
来自到机房一位巨佬的启发。
对于每个点有 \(4\) 种状态。
- 1.之前没买过，当前点买。
- 2.之前没买过，当前点不买。
- 3.之前点买过，当前点卖。
- 4.之前点买过，当前点不卖。
在精简一下：
- 1.当前点买。
- 2.当前点卖。
那么根据这些状态我们就可以尝试分层了。
首先原图看做是边权均为 \(0\) 的图。
然后，如果想要到达状态 \(1\) ，则一定通过最初状态。
那我们将原图向图 \(2\) 连条有向边，指向图 \(2\)。这些边的代价为原图上的点的点权的相反数（你买相当于是扣钱嘛。
如果你想到达状态 \(2\)，则一定通过状态 \(1\)。你手上必须要有宝石你才能卖a。
于是将图 \(2\) 像图 \(3\) 连条有向边，指向图 \(3\)。这些边的代价为图 \(2\) 所对应的原图上的点的点权。（你又赚回来了。
最后我们规定终点为 \(n * 3 + 1\)。
则原图上的 \(n\) 需要与终点连边（你可以不买也不卖。
图 \(2\) 上的 \(n\) 不需要与终点连边（点权保证为正，所以买了不卖的情况一定不是最优解。
图 \(3\) 上的 \(n\) 需要与终点连边（正常情况对吧。
于是乎。
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXE = 5e5 + 5;
const int INF = 0x3f3f3f3f;
int len = 0, head[MAXN * 3 + 5];
struct edge {
int to, next, w;
edge() {}
edge(int To, int Next, int W) {
to = To;
next = Next;
w = W;
}
} e[MAXE * 3 + 5];
void Add_Edge(int x, int y, int c) {
e[++len].to = y;
e[len].w = c;
e[len].next = head[x];
head[x] = len;
}
int w[MAXN * 3 + 5], n, m;
void Add_Extra(int x, int y, int c) {
Add_Edge(x, y, 0);
Add_Edge(x + n, y + n, 0);
Add_Edge(x + 2 * n, y + 2 * n, 0);
Add_Edge(x, y + n, -c);
Add_Edge(x + n, y + 2 * n, c);
}
int dist[MAXN * 3 + 5];
bool vis[MAXN * 3 + 5];
void spfa() {
memset(dist, -INF, sizeof dist);
queue<int> q;
vis[1] = true;
dist[1] = 0;
q.push(1);
while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to, cost = e[i].w;
if(dist[v] < dist[u] + cost) {
dist[v] = dist[u] + cost;
if(!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
}
int main() {
scanf ("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
scanf ("%d", &w[i]);
for(int i = 1; i <= m; i++) {
int u, v, flag;
scanf ("%d %d %d", &u, &v, &flag);
Add_Extra(u, v, w[u]);
if(flag == 2)
Add_Extra(v, u, w[v]);
}
Add_Edge(n, n * 3 + 1, 0);
Add_Edge(n + n * 2, n * 3 + 1, 0);
n *= 3;
n++;
spfa();
printf("%d\n", dist[n]);
return 0;
}