[CODEVS 1173] 最优贸易

描述

分析

官方解法

先考虑如果题目中的线路不会构成环, 那么问题可以简化成一个DP就可以解决的问题=> 先正着DP, 找出在每个点之前可以买进的最低的价格 minp ; 再倒着DP, 统计出在每个点之后可以卖出的最高价格 maxp , 取所有点中的minp – maxp 的最大值就是最大的收益.

现在的问题就是解决环的存在, 因为有环的话没有一个拓扑序供我们DP使用. 所以用Tarjan算法求强联通分量缩点, 同时统计出缩点后每个点的最低买入价和最高卖出价, 重新建图, DP即可.

PS: 不会写……

民间解法

其实我最初想练的是官方的解法, 因为向鹏达刚讲了这种方法. 结果DP写不出来了, 就用BFS写拓扑排序. 发现还需要写一个逆向的拓扑排序. 写着写着发现没必要缩点了, 接着就YY出了民间的两遍SPFA的做法. 都说是SPFA, 其实我觉得也不象SPFA. 另外还需要注意不能考虑不在s-t路径上的点, SPFA同时判即可.

代码

381ms 10MB

using namespace std;const int INF = 1e7 + 7;const int maxn = 100000 + 10;queue<int> Q;vector<int> G1[maxn], G2[maxn];int price[maxn], minp[maxn], maxp[maxn];bool inq[maxn], vis1[maxn], vis2[maxn];void AddEdge(int s, int t) {G1[s].push_back(t);G2[t].push_back(s);}int SPFA1(int s) {memset(inq, 0, sizeof(inq));Q.push(s); vis1[s] = inq[s] = 1;minp[s] = price[s];while(!Q.empty()) {int u = Q.front(); Q.pop();inq[u] = 0;for(int i = 0; i < G1[u].size(); i++) {int v = G1[u][i];if(minp[v] > minp[u]) {minp[v] = minp[u];if(!inq[v]) Q.push(v);if(!vis1[v]) {vis1[v] = 1;minp[v] = min(minp[v], price[v]);}}}}}int SPFA2(int s) {memset(inq, 0, sizeof(inq));Q.push(s); vis2[s] = inq[s] = 1;maxp[s] = price[s];while(!Q.empty()) {int u = Q.front(); Q.pop();inq[u] = 0;for(int i = 0; i < G2[u].size(); i++) {int v = G2[u][i];if(maxp[v] < maxp[u]) {maxp[v] = maxp[u];if(!inq[v]) Q.push(v);if(!vis2[v]) {vis2[v] = 1;maxp[v] = max(maxp[v], price[v]);}}}}}int main() {int n, m;scanf(“%d%d”, &n, &m);for(int i = 0; i < n; i++) {scanf(“%d”, &price[i]);minp[i] = INF;maxp[i] = -1;}for(int i = 0; i < m; i++) {int u, v, state;scanf(“, &u, &v, &state);u–; v–;AddEdge(u, v);if(state == 2) AddEdge(v, u);}SPFA1(0);SPFA2(n-1);int ans = 0;for(int i = 0; i < n; i++) if(vis1[i] && vis2[i]) // 注意判断ans = max(ans, maxp[i] – minp[i]);printf(“%d\n”, ans);return 0;}

，会让你的心态更平和更坦然，也会让你心无旁骛，更会让你的心灵得到解脱和抚慰。