[NOIP2009 T3]最优贸易(分层图spfa / 两次spfa / tarjan + topo)

题目

描述

$C$ 国有 $n$ 个大城市和 $m$ 条道路,每条道路连接这 $n$ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $m$ 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为 $1$ 条。
$C$ 国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 $C$ 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后,便决定在旅游的同时,利用商品在不同城市中的差价赚回一点旅费。设 $C$ 国 n 个城市的标号从 $1 \sim n$ ,阿龙决定从 $1$ 号城市出发,并最终在 $n$ 号城市结束自己的旅行。在旅游的过程中,任何城市可以重复经过多次,但不要求经过所有 $n$ 个城市。阿龙通过这样的贸易方式赚取旅费:他会选择一个经过的城市买入他最喜欢的商品――水晶球,并在之后经过的另一个城市卖出这个水晶球,用赚取的差价当做旅费。由于阿龙主要是来 $C$ 国旅游,他决定这个贸易只进行最多一次,当然,在赚不到差价的情况下他就无需进行贸易。
现在给出 $n$ 个城市的水晶球价格, $m$ 条道路的信息(每条道路所连接的两个城市的编号以及该条道路的通行情况)。请你告诉阿龙,他最多能赚取多少旅费。

输入

第一行包含 $2$ 个正整数 $n$ 和 $m$ ,中间用一个空格隔开,分别表示城市的数目和道路的数目。
第二行 $n$ 个正整数,每两个整数之间用一个空格隔开,按标号顺序分别表示这 $n$ 个城市的商品价格。
接下来 $m$ 行,每行有 $3$ 个正整数 $x,y,z$ ,每两个整数之间用一个空格隔开。如果 $z=1$ ,表示这条道路是城市 $x$ 到城市 $y$ 之间的单向道路;如果 $z=2$ ,表示这条道路为城市 $x$ 和城市 $y$ 之间的双向道路。

输出

一 个整数,表示最多能赚取的旅费。如果没有进行贸易,则输出 $0$ 。

输入样例

1
2
3
4
5
6
7
5 5 
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2

输出样例

1
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≤21≤z≤2 , $1≤$ 各城市水晶球价格 $≤100$ 。


解题思路(共3种方法)

法1——分层图spfa

分层图是一个神奇的东西,建的好可以大大简化题目。
针对这道题,我们可以把图分三层:

  • 第一层表示买之前,第二层表示买之后卖之前,第三层表示卖之后;
  • 每一层内部边权设为 $0$;
  • 对于一个点 $i$,设 $i$ 能到 $j$,则从 $i$ 连一条边权为 $-v[i]$ 的单向边到 $j+n$(即 $j$ 在第二层图中对应的点),表示在 $i$ 买入后走到 $j$;
  • 同理,从 $i+n$ 连一条边权为 $v[i]$ 的单向边到 $j+n+n$(即 $j$ 在第三层图中对应的点),表示在 $i$ 卖出后走到 $j$;
  • 最后将 $n$ 和 $n+n+n$ 都连向一个终点 $T$。

那么,从 $1$ 出发到 $T$,要么一直在第一层中移动,表示没有进行买卖;要么从第一层经过第二层到达第三层,表示经过了一次买卖操作。可以发现,这样我们就把所有买卖情况考虑到了,因此,最后做一个简单的spfa找最长路即可。

法2——两次spfa

设 $minPrice[i]$ 表示从 $1$ 到 $i$ 的路线中经过的最小价格,$maxPrice[i]$ 表示从 $i$ 到 $n$ 的路线中经过的最大价格,那么 $ans = \max\limits_{i=1}^{n} (maxPrice[i]-minPrice[i])$
可以先正向用 spfa 求出 $minPrice$,再反向用 spfa 求出 $maxPrice$

法3——tarjan+topo

从50%的数据范围中得到启发,如果原图是一个DAG,那么我们可以用拓扑序得到答案:用拓扑序遍历该图,同时记录下历史最小价格,每到一个点用它的价格减去历史最小价格来更新答案,最后就能得到最大利润了。
但是原图可能存在环,怎么办?我们可以用 tarjan 缩点。因为在同一个强连通分量中可以随意走动,所以缩点后新点的最低价格就是强连通分量中的最低价格,新点的最高价格就是强连通分量中的最高价格,于是我们成功把图转成了一个DAG,就可以用上述方法解决问题了。


Code#1

分层图spfa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# include<cstdio>
# include<queue>

using namespace std;

const int N = 100005;
const int M = 500005;
const int INF = 1e9;
int n, m, v[N], x, y, z, T, S;

struct Edge{
int nxt, to, dis;
}edge[M<<2];
int head[N*3], edgeNum;
void addEdge(int from, int to, int dis){
edge[++edgeNum].nxt = head[from];
edge[edgeNum].to = to;
edge[edgeNum].dis = dis;
head[from] = edgeNum;
}

int dis[N*3];
bool inq[N*3];
void spfa(){
for(int i = 1; i <= n * 3; i++)
dis[i] = -INF;
queue<int> q;
q.push(S);
dis[S] = 0;
inq[S] = 1;
while(!q.empty()){
int cur = q.front(); q.pop(); inq[cur] = 0;
for(int i = head[cur]; i; i = edge[i].nxt){
if(dis[edge[i].to] < dis[cur] + edge[i].dis){
dis[edge[i].to] = dis[cur] + edge[i].dis;
if(!inq[edge[i].to]){
q.push(edge[i].to);
inq[edge[i].to] = 1;
}
}
}
}
}

int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &x, &y, &z);
addEdge(x, y, 0);
addEdge(x+n, y+n, 0);
addEdge(x+n+n, y+n+n, 0);
addEdge(x, y+n, -v[x]);
addEdge(x+n, y+n+n, v[x]);
if(z == 2){
addEdge(y, x, 0);
addEdge(y+n, x+n, 0);
addEdge(y+n+n, x+n+n, 0);
addEdge(y, x+n, -v[y]);
addEdge(y+n, x+n+n, v[y]);
}
}
S = 1, T = n+n+n+1;
addEdge(n, T, 0);
addEdge(n+n+n, T, 0);
spfa();
printf("%d\n", dis[T]);
return 0;
}

Code#2

两次spfa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
# include<algorithm>
# include<cstring>
# include<cstdio>
# include<queue>

using namespace std;

const int MAXN = 100005;
const int MAXM = 500005;
int n, m, p[MAXN], u, v, q, ans;

struct Edge{
int nxt, to;
}edge[MAXM<<1], fedge[MAXM<<1];

int head[MAXN], edge_num;
int fhead[MAXN], fedge_num;
void add_edge(int from, int to){
edge[++edge_num].nxt = head[from];
edge[edge_num].to = to;
head[from] = edge_num;
fedge[++fedge_num].nxt = fhead[to];
fedge[fedge_num].to = from;
fhead[to] = fedge_num;
}

int max_price[MAXN], min_price[MAXN];
bool inq[MAXN];
void spfa1(){
memset(inq, 0, sizeof inq);
memset(min_price, 0x7f, sizeof min_price);
queue<int> q;
q.push(1);
inq[1] = 1;
min_price[1] = p[1];
while(!q.empty()){
int cur = q.front(); q.pop(); inq[cur] = 0;
for(int i = head[cur]; i; i = edge[i].nxt){
if(min_price[edge[i].to] > min(min_price[cur], p[edge[i].to])){
min_price[edge[i].to] = min(min_price[cur], p[edge[i].to]);
if(!inq[edge[i].to]){
q.push(edge[i].to);
inq[edge[i].to] = 1;
}
}
}
}
}

void spfa2(){
memset(inq, 0, sizeof inq);
memset(max_price, 0, sizeof max_price);
queue<int> q;
q.push(n);
inq[n] = 1;
max_price[n] = p[n];
while(!q.empty()){
int cur = q.front(); q.pop(); inq[cur] = 0;
for(int i = fhead[cur]; i; i = fedge[i].nxt){
if(max_price[fedge[i].to] < max(max_price[cur], p[fedge[i].to])){
max_price[fedge[i].to] = max(max_price[cur], p[fedge[i].to]);
if(!inq[fedge[i].to]){
q.push(fedge[i].to);
inq[fedge[i].to] = 1;
}
}
}
}
}

int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &u, &v, &q);
add_edge(u, v);
if(q == 2) add_edge(v, u);
}
spfa1();
spfa2();
for(int i = 1; i <= n; i++) ans = max(ans, max_price[i] - min_price[i]);
printf("%d", ans);
return 0;
}

Code#3

tarjan+topo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# include<cstring>
# include<cstdio>
# include<stack>
# include<queue>

using namespace std;

const int MAXM = 500005;
const int MAXN = 100005;
int n, m, x, y, z, p[MAXN], minprice = 0x7fffffff, maxp[MAXN], minp[MAXN];

inline int max(int a, int b){
return a > b ? a : b;
}

inline int min(int a, int b){
return a < b ? a : b;
}

struct Edge{
int nxt, to;
}edge[MAXM<<1], e[MAXM<<1], fe[MAXM<<1];

int head[MAXN], edge_num;
int fh[MAXN], fe_n;
void add_edge(int from, int to){
edge[++edge_num].nxt = head[from];
edge[edge_num].to = to;
head[from] = edge_num;
fe[++fe_n].nxt = fh[to];
fe[fe_n].to = from;
fh[to] = fe_n;
}

bool vis[MAXN];
void dfs(int x){
vis[x] = 1;
for(int i = fh[x]; i; i = fe[i].nxt){
if(!vis[fe[i].to]) dfs(fe[i].to);
}
}

int h[MAXN], e_n, ind[MAXN];
void a_e(int from, int to){
e[++e_n].nxt = h[from];
e[e_n].to = to;
h[from] = e_n;
ind[to]++;
}

int low[MAXN], dfn[MAXN], belong[MAXN], scc, dex;
bool ins[MAXN];
stack<int> s;
void tarjan(int x){
s.push(x);
ins[x] = 1;
low[x] = dfn[x] = ++dex;
for(int i = head[x]; i; i = edge[i].nxt){
if(!vis[edge[i].to]) continue;
if(!dfn[edge[i].to]){
tarjan(edge[i].to);
low[x] = min(low[x], low[edge[i].to]);
}
else if(ins[edge[i].to]) low[x] = min(low[x], dfn[edge[i].to]);
}
if(low[x] == dfn[x]){
scc++;
while(1){
int cur = s.top(); s.pop();
ins[cur] = 0;
belong[cur] = scc;
maxp[scc] = max(maxp[scc], p[cur]);
minp[scc] = min(minp[scc], p[cur]);
if(cur == x) break;
}
}
}

int f[MAXN], ans;
void topo(){
queue<int> q;
for(int s = 1; s <= scc; s++)
if(!ind[s])
q.push(s);
while(!q.empty()){
int cur = q.front(); q.pop();
for(int i = h[cur]; i; i = e[i].nxt){
ind[e[i].to]--;
if(!ind[e[i].to]){
q.push(e[i].to);
minprice = min(minprice, minp[e[i].to]);
ans = max(ans, maxp[e[i].to] - minprice);
}
}
}
}

int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &p[i]);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &x, &y, &z);
add_edge(x, y);
if(z == 2) add_edge(y, x);
}
dfs(n);
memset(maxp, 0, sizeof maxp);
memset(minp, 0x7f, sizeof minp);
for(int i = 1; i <= n; i++)
if(!dfn[i] && vis[i])
tarjan(i);
for(int i = 1; i <= n; i++)
for(int j = head[i]; j; j = edge[j].nxt)
if(vis[edge[j].to] && belong[edge[j].to] != belong[i])
a_e(belong[i], belong[edge[j].to]);
topo();
printf("%d\n", ans);
return 0;
}