「NOIP2009」最优贸易 题解
题目描述
\(C\)国有\(n\)个大城市和\(m\)条道路，每条道路连接这\(n\)个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这\(m\)条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为\(1\)条。
\(C\)国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到\(C\)国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设\(C\)国 n 个城市的标号从\(1- n\)，阿龙决定从\(1\)号城市出发，并最终在\(n\) 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有\(n\)个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来\(C\)国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设\(C\)国有\(5\)个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。
假设\(1-n\)号城市的水晶球价格分别为\(4,3,5,6,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\)。
NOIP 2009 提高组 第三题
思路（Tarjan缩点+拓扑排序+DP）
首先来考虑如果该图为DAG的情况（每个点所在集合为自己）。
（maxn[i] 表示在i点时最大卖出价格，minn[i] 表示在i点时最小进价）
可以借用拓扑排序进行DP实行状态转移， 找到1号点能到达的点的答案。在拓扑排序中，有两点u，v满足，有一条边u到v，如果u被访问过（即是已经求出到达该点的最优解），则将v置为已访问（先将1所在集合记为访问过），进行对于u到v的状态转移。
更新在v点买进的最小进价：
minn[v]=min(minn[v],minn[u])
更新在走到v点时的最优解：
dp[v]=max(dp[u],dp[v],maxn[v]-minn[v])
最后拓扑排序结束之后，答案就存在dp[belong[i]]中了。
但是，题目中说了会有环
所以，先对该图进行Tarjan缩点，对于旧图建一张新图，将其变为DAG。
我们需要初始化：
maxn[i]为所有属于i集合的点的价值最大值
minn[i]为所有属于i集合的点的价值最小值
然后进行上述DAG中的操作即可。
C++代码：
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
vector<int> v[MAXN], Dag[MAXN];
stack<int> s;
queue<int> q;
int dfn[MAXN], low[MAXN], belong[MAXN], elem[MAXN];
bool instack[MAXN], vis[MAXN];
int tim, cnt_set;
int w[MAXN], maxn[MAXN], minn[MAXN], in[MAXN], dp[MAXN];
int n, m, ans;
void Read();
void Tarjan(int);
void Build();
void Topo();
int main() {
Read();
Build();
Topo();
return 0;
}
void Topo() {
vis[belong[1]] = 1;
for(int i = 1; i <= cnt_set; i++)
if(!in[i])
q.push(i);
while(!q.empty()) {
int now = q.front(); q.pop();
int SIZ = Dag[now].size();
for(int i = 0; i < SIZ; i++) {
int next = Dag[now][i];
if(vis[now]) {
vis[next] = 1;
minn[next] = min(minn[next], minn[now]);
dp[next] = max(dp[now], max(dp[next], maxn[next] - minn[next]));
}
if(!(--in[next]))
q.push(next);
}
}
printf("%d", dp[belong[n]]);
}
void Build() {
for(int i = 1; i <= n; i++)
if(!dfn[i])
Tarjan(i);
memset(minn, 0x7f, sizeof(minn));
for(int i = 1; i <= n; i++) {
maxn[belong[i]] = max(maxn[belong[i]], w[i]);
minn[belong[i]] = min(minn[belong[i]], w[i]);
}
for(int i = 1; i <= n; i++) {
int SIZ = v[i].size();
for(int j = 0; j < SIZ; j++) {
int next = v[i][j];
if(belong[i] != belong[next]) {
Dag[belong[i]].push_back(belong[next]);
in[belong[next]]++;
}
}
}
}
void Tarjan(int now) {
low[now] = dfn[now] = ++tim;
instack[now] = true;
s.push(now);
int SIZ = v[now].size();
for(int i = 0; i < SIZ; i++) {
int next = v[now][i];
if(!dfn[next]) {
Tarjan(next);
low[now] = min(low[now], low[next]);
}
else if(instack[next])
low[now] = min(low[now], dfn[next]);
}
if(dfn[now] == low[now]) {
cnt_set += 1;
int Top = -1;
while(!s.empty() && Top != now) {
elem[cnt_set]++;
Top = s.top();
belong[Top] = cnt_set;
instack[Top] = false;
s.pop();
}
}
}
void Read() {
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, F;
scanf("%d %d %d", &U, &V, &F);
if(F == 1)
v[U].push_back(V);
else {
v[U].push_back(V);
v[V].push_back(U);
}
}
}
该方法的时间复杂度就是\(O(n+m)\)。
因为\(m>n\)，时间复杂度就可以算作\(O(m)\)