描述

http://www.codevs.cn/problem/1173/

---

分析

官方解法

先考慮如果題目中的線路不會(huì)構(gòu)成環(huán), 那么問(wèn)題可以簡(jiǎn)化成一個(gè)DP就可以解決的問(wèn)題=>
先正著DP, 找出在每個(gè)點(diǎn)之前可以買(mǎi)進(jìn)的最低的價(jià)格 minp ; 再倒著DP, 統(tǒng)計(jì)出在每個(gè)點(diǎn)之后可以賣(mài)出的最高價(jià)格 maxp , 取所有點(diǎn)中的minp - maxp 的最大值就是最大的收益.

現(xiàn)在的問(wèn)題就是解決環(huán)的存在, 因?yàn)橛协h(huán)的話沒(méi)有一個(gè)拓?fù)湫蚬┪覀僁P使用. 所以用Tarjan算法求強(qiáng)聯(lián)通分量縮點(diǎn), 同時(shí)統(tǒng)計(jì)出縮點(diǎn)后每個(gè)點(diǎn)的最低買(mǎi)入價(jià)和最高賣(mài)出價(jià), 重新建圖, DP即可.

PS: 不會(huì)寫(xiě)……

民間解法

其實(shí)我最初想練的是官方的解法, 因?yàn)橄蝙i達(dá)剛講了這種方法. 結(jié)果DP寫(xiě)不出來(lái)了, 就用BFS寫(xiě)拓?fù)渑判? 發(fā)現(xiàn)還需要寫(xiě)一個(gè)逆向的拓?fù)渑判? 寫(xiě)著寫(xiě)著發(fā)現(xiàn)沒(méi)必要縮點(diǎn)了, 接著就YY出了民間的兩遍SPFA的做法.
都說(shuō)是SPFA, 其實(shí)我覺(jué)得也不象SPFA.
另外還需要注意不能考慮不在s-t路徑上的點(diǎn), SPFA同時(shí)判即可.

---

代碼

381ms 10MB

#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> 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("%d%d%d", &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; }

總結(jié)

以上是生活随笔為你收集整理的[CODEVS 1173] 最优贸易的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。