題目描述
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 之間的雙向道路。
輸出格式
輸出檔案共 1 行，包含 1 個整數，表示最多能賺取的旅費。如果沒有進行貿易，則輸出 0 。
樣例資料 1
輸入
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。
解析：
對于50%的資料，顯然可以用DP。
令
表示點
到終點之間的最大價格，于是答案為
。
對于100%的資料，其實50%的資料就已經提示了我們，不過變化在于有了雙向邊，是以不能直接進行遞推，我當時就是卡在這個地方。後來向dalao請教後猛然驚醒，我們可以強制将整個圖變成有向圖啊！
怎麼強制變成有向圖？用Tarjan進行縮點重建立圖，這樣整個圖就沒有環了，就可以直接進行遞推了。
因為一個強連通分量中兩點的買入賣出順序可以互換，是以對答案無影響。
代碼：
#include <bits/stdc++.h>
using namespace std;
const int Maxn=100005;
const int Maxm=500005;
pair<int,int>q;
int n,m,size,cnt,sum,ans,Index,tot;
int f[Maxn],first[Maxn],First[Maxn],c[Maxn];
int low[Maxn],num[Maxn],father[Maxn],vis[Maxn],p[Maxn],maxx[Maxn];
struct shu{int to,next;};
shu edge[Maxm<<1],Edge[Maxm<<1];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void build(int x,int y)
{
edge[++size].next=first[x];
first[x]=size;
edge[size].to=y,edge[size];
}
inline void Build(int x,int y)
{
Edge[++size].next=First[x];
First[x]=size;
Edge[size].to=y,Edge[size];
}
inline void tarjan(int point)
{
low[point]=num[point]=++Index;
vis[point]=1,p[++tot]=point;
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(!num[to]) tarjan(to),low[point]=min(low[point],low[to]);
else if(vis[to]) low[point]=min(low[point],num[to]);
}
if(low[point]==num[point])
{
cnt++;
while(1)
{
int x=p[tot--];
vis[x]=0,father[x]=cnt,maxx[cnt]=max(maxx[cnt],c[x]);
if(x==point) break;
}
}
}
inline void dfs(int point,int fa)
{
vis[point]=1;
for(int u=First[point];u;u=Edge[u].next)
{
int to=Edge[u].to;
if(vis[to]) continue;
f[to]=max(maxx[to],f[point]);
dfs(to,point);
}
}
int main()
{
n=get_int(),m=get_int();
for(int i=1;i<=n;i++) c[i]=get_int();
for(int i=1;i<=m;i++)
{
int x=get_int(),y=get_int(),z=get_int();
build(x,y);
if(z==2) build(y,x);
}
for(int i=1;i<=n;i++) if(!num[i]) tarjan(i);
for(int i=1;i<=n;i++)
for(int u=first[i];u;u=edge[u].next)
if(father[edge[u].to]!=father[i])
Build(father[edge[u].to],father[i]);
f[father[n]]=maxx[father[n]];
dfs(father[n],0);
for(int i=1;i<=n;i++) if(vis[father[i]]) ans=max(ans,f[father[i]]-c[i]);
cout<<ans;
return 0;
}