https://www.luogu.org/problemnew/show/P1073

C國有 n n個大城市和 mm 條道路，每條道路連接這 nn個城市中的某兩個城市。任意兩個城市之間最多只有一條道路直接相連。這 mm 條道路中有一部分為單向通行的道路，一部分為雙向通行的道路，雙向通行的道路在統(tǒng)計條數時也計為 1 1條。C C國幅員遼闊，各地的資源分布情況各不相同，這就導致了同一種商品在不同城市的價格不一定相同。但是，同一種商品在同一個城市的買入價和賣出價始終是相同的。商人阿龍來到 CC 國旅游。當他得知同一種商品在不同城市的價格可能會不同這一信息之后，便決定在旅游的同時，利用商品在不同城市中的差價賺回一點旅費。設 CC 國 n 個城市的標號從 1~ n1 n，阿龍決定從 1 1號城市出發(fā)，并最終在 nn 號城市結束自己的旅行。在旅游的過程中，任何城市可以重復經過多次，但不要求經過所有 nn 個城市。阿龍通過這樣的貿易方式賺取旅費：他會選擇一個經過的城市買入他最喜歡的商品――水晶球，并在之后經過的另一個城市賣出這個水晶球，用賺取的差價當做旅費。由于阿龍主要是來 CC 國旅游，他決定這個貿易只進行最多一次，當然，在賺不到差價的情況下他就無需進行貿易。假設 C C國有 55個大城市，城市的編號和道路連接情況如下圖，單向箭頭表示這條道路為單向通行，雙向箭頭表示這條道路為雙向通行。假設 1~n1 n 號城市的水晶球價格分別為 4,3,5,6,14,3,5,6,1。阿龍可以選擇如下一條線路：11->22->33->55，并在 2 2號城市以 33 的價格買入水晶球，在 33號城市以 5 5的價格賣出水晶球，賺取的旅費數為 2。阿龍也可以選擇如下一條線路 11->44->55->44->55，并在第1 1次到達 55 號城市時以 1 1的價格買入水晶球，在第 22 次到達 44 號城市時以 66 的價格賣出水晶球，賺取的旅費數為 55。現(xiàn)在給出 n n個城市的水晶球價格，mm 條道路的信息（每條道路所連接的兩個城市的編號以及該條道路的通行情況）。請你告訴阿龍，他最多能賺取多少旅費。 題意

?

第一眼看覺得是先縮點然后DAG圖上跑一邊拓撲排序，除了敲起來手有點酸之外沒有什么難度。就直接過了。

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 1e5 + 10; const int maxm = 5e5 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int val[maxn]; struct Edge{int to,next; }edge[maxm * 2]; int head[maxn],tot; void init(){for(int i = 0 ; i <= N + 1; i ++) head[i] = -1;tot = 0; } void add(int u,int v){edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; } int Low[maxn],dfn[maxn],Stack[maxn],Belong[maxn],num[maxn]; int Index,top,scc; bool Instack[maxn]; void Tarjan(int u){int v;Low[u] = dfn[u] = ++Index;Stack[top++] = u;Instack[u] = true;for(int i = head[u]; ~i; i = edge[i].next){v = edge[i].to;if(!dfn[v]){Tarjan(v);if(Low[u] > Low[v]) Low[u] = Low[v];}else if(Instack[v] && Low[u] > dfn[v]){Low[u] = dfn[v];}}if(Low[u] == dfn[u]){scc++;do{v = Stack[--top];Instack[v] = false;Belong[v] = scc;num[scc]++;}while(v != u);} } int MAX[maxn],MIN[maxn],ind[maxn],ans[maxn]; vector<int>P[maxn]; int main(){Sca2(N,M); init();for(int i = 1; i <= N ; i ++) Sca(val[i]);for(int i = 1; i <= M ; i ++){int u,v,w; Sca3(u,v,w);add(u,v);if(w == 2) add(v,u);}for(int i = 1; i <= N ; i ++) if(!dfn[i]) Tarjan(i);for(int i = 1; i <= scc; i ++){MAX[i] = -INF; MIN[i] = INF;}for(int i = 1; i <= N ; i ++){int u = Belong[i];MAX[u] = max(MAX[u],val[i]);MIN[u] = min(MIN[u],val[i]);for(int j = head[i]; ~j; j = edge[j].next){int v = Belong[edge[j].to];if(u == v) continue;P[u].push_back(v);ind[v]++; }}queue<int>Q;for(int i = 1; i <= scc; i ++) if(!ind[i]) Q.push(i);while(!Q.empty()){int u = Q.front(); Q.pop();ans[u] = max(ans[u],MAX[u] - MIN[u]);for(int i = 0; i < P[u].size(); i ++){int v = P[u][i];ind[v]--;MIN[v] = min(MIN[v],MIN[u]);ans[v] = max(ans[v],ans[u]);if(!ind[v]) Q.push(v);}}Pri(ans[Belong[N]]);return 0; } 縮點 + 拓撲排序

?

后來發(fā)現(xiàn)還有一種更加新奇的解法，構造分層圖，將原圖變?yōu)橐粋€帶權圖，權的意思是商人走這條路要得到的錢（負數代表花費），一開始的圖所有邊權都是0，表示這個商人什么也不買，走來走去不虧也不賺。然后我們對于每個點v，構造一條邊通向v + N,邊權為-val[v],表示商人在這個點買了一個水晶球，1 + N ~ N + N就是出現(xiàn)的第二個圖，對于第二圖，也像第一條路一樣構造出相同的邊權為0的邊，表示商人買了水晶球之后依然可以不買也不賣的在這個圖上走來走去，同理，我們再v + N ~ v + N + N構造一條邊權為val[v]的邊，表示商人買完之后在這個點又賣出去了，同第二個圖一樣，構造出第三個圖，最后題意要求到達終點，所以可取的點只有N和3 * N,即第一個圖和第三個圖的終點，跑一邊最短長路即可。

由于邊權有正有負的，不能用Dijkstra跑，無向圖也不可以拓撲排序dp，所以只能SPFA（大概是這個做法的唯一缺點）

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 3e5 + 10; const int maxm = 2e6 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int head[maxn],tot; struct Edge{int to,next,dis; }edge[maxm]; void init(){for(int i = 0 ; i <= 3 * N + 1; i ++) head[i] = -1;tot = 0; } void add(int u,int v,int w){edge[tot].to = v;edge[tot].next = head[u];edge[tot].dis = w;head[u] = tot++; } int val[maxn]; int dis[maxn],vis[maxn]; int SPFA(int s,int t){for(int i = 0 ; i <= 3 * N + 1; i ++) dis[i] = -INF;dis[1] = 0;queue<int>Q;Q.push(s);while(!Q.empty()){int u = Q.front(); Q.pop();vis[u] = 0;for(int i = head[u]; ~i ; i = edge[i].next){int v = edge[i].to;if(dis[v] < dis[u] + edge[i].dis){dis[v] = dis[u] + edge[i].dis;if(!vis[v]){vis[v] = 1;Q.push(v);}}} }if(dis[t] == -INF) dis[t] = 0;return dis[t]; } int main(){Sca2(N,M); init();for(int i = 1; i <= N ; i ++){Sca(val[i]);add(i,i + N,-val[i]);add(i + N,i + N + N,val[i]);} for(int i = 1; i <= M ; i ++){int u,v,w; Sca3(u,v,w);add(u,v,0);add(u + N,v + N,0);add(u + N + N,v + N + N,0);if(w == 2){add(v,u,0);add(v + N,u + N,0);add(v + N,u + N + N,0);} }int t = 3 * N + 1,s = 1;add(N,t,0); add(3 * N,t,0);Pri(SPFA(s,t));return 0; }

?

轉載于:https://www.cnblogs.com/Hugh-Locke/p/10330356.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的洛谷P1073 Tarjan + 拓扑排序 // 构造分层图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。