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

发表于 更新于 分类于 ， ， ，
NOIP2009 T3

题目

描述

$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;
}