題意：從1-n的一條路徑中，找出兩點，使得兩點權值之差最大。n個點不一定要都經過。

解題思路：這道題實際可以轉化為找出可達的兩點a，b，使得a和b兩點的權值之差最大。。。這道題確實很難想到是轉化為最短路的模型，我開始還是按照論壇里面說的，先求強連通分量、縮點，最后再搜索，結果掛了。。

假設最后的結果是a-b，那么我們肯定要保證a>b，否則根據題意就無意義。并且我們還應該要有b->a，即可以從b走到a，那么就定義兩個數組d_min[i]，和d_max[i]，分別表示從1->i經過點的最小值和從i->n經過點的最大值，最后只需找到最大的d_max[i] - d_min[i]即可。為了方便求d_max[i]，我們應該要從n出發尋找，所以應該要建立反向邊。

注意：這里是能夠保證我們之前講的兩條性質，注意到d_min和d_max表示的意義，是1->i和i->n所經過的點的最小和最大值，如果a在b的前面，那么肯定d_max和d_min不會同時包含a和b的（畫圖即可明白），如果a<b，毫無疑問肯定算出的不會是最優值。

這里算d_min和d_max可以用spfa算法，確實spfa算法在最短路里面的應用非常廣。總之這樣運用spfa還是第一次見。。。

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const int maxn = 100005; struct Edge {int k,next; }edge[maxn<<2]; int n,m,cnt,d_max[maxn],d_min[maxn]; int head1[maxn],head2[maxn]; bool s1[maxn],s2[maxn];void addedge(int u,int v) {edge[cnt].k = v;edge[cnt].next = head1[u];head1[u] = cnt++;edge[cnt].k = u;edge[cnt].next = head2[v];head2[v] = cnt++; }void spfa() {queue<int> q;memset(s1,false,sizeof(s1));memset(s2,false,sizeof(s2));q.push(1);s1[1] = true;while(!q.empty()){int t = q.front();q.pop();for(int i = head1[t]; i != -1; i = edge[i].next){int k = edge[i].k;d_min[k] = min(d_min[t],d_min[k]);if(s1[k] == false){s1[k] = true;q.push(k);}}}q.push(n);s2[n] = true;while(!q.empty()){int t = q.front();q.pop();for(int i = head2[t]; i != -1; i = edge[i].next){int k = edge[i].k;d_max[k] = max(d_max[t],d_max[k]);if(s2[k] == false){s2[k] = true;q.push(k);}}}int ans = 0;for(int i = 1; i <= n; i++)if(s1[i] && s2[i]){ans = max(ans,d_max[i] - d_min[i]);}printf("%d\n",ans); }int main() {while(scanf("%d%d",&n,&m)!=EOF){memset(head1,-1,sizeof(head1));memset(head2,-1,sizeof(head2));cnt = 0;for(int i = 1; i <= n; i++){scanf("%d",&d_max[i]);d_min[i] = d_max[i];}for(int i = 1; i <= m; i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);addedge(x,y);if(z == 2)addedge(y,x);}spfa();}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 247的全部內容，希望文章能夠幫你解決所遇到的問題。

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