题解 P1073 【最优贸易】
有兴趣的同学可以去我博客看：http://www.cnblogs.com/bingdada/p/7699611.html
思路：
一开始读题目想到的就是跟强联通分量有关。
然而事实上，好多人用的是两遍SPFA， 但仔细想想....... 我还是用我一开始的思路吧。
我的做法就是先将题目给出的图进行tarjan缩点，然后再拓扑排序，之后再DP。
很明显的，在同一个强联通分量里面的每个城市都是可以多次经过的，于是，我们在求强联通分量的过程中记录当前强联通分量里点的最大值（maxx），最小值（minx)，与最大值与最小值之差（利润）(maxcost)。
在这之后，我们对图进行缩点，缩点之后新图是DAG（有向无环图），之后就进行DP。
我们设dp[i]为 新图中1所对应的强联通分量编号到 强联通分量编号为i的点能获得的最大利润。
设mincost[i]为新图中1所对应的强联通分量编号到 强联通分量编号为i的点的最小点值。
则在更行dp前我们先更新mincost (假设当前是从j点到i点) ：mincost[i] = min(mincost[j],minx[i]);
之后再进行状态转移： dp[i] = max( max(dp[i],dp[j]) , max(maxcost[i],maxx[i]-mincost[i]) );
在最后返回原图节点n所属的强联通节点编号 的dp值就行。
下面贴代码，主要细节已注释，有问题给我留言。
#include<cstdio>
#include<algorithm>
#define N 100009
#define M 700009
using namespace std;
int en,en1,n;
struct edge{
int e;
edge *next;
}*v[N],*v1[N],ed[M],ed1[M];
void add_edge(int s,int e){ //旧图
en++;
ed[en].next = v[s],v[s] = ed+en,v[s]->e =e;
}
void add_edge1(int s,int e){ //新图
en1++;
ed1[en1].next = v1[s],v1[s] = ed1+en1,v1[s]->e =e;
}
int t,cnt,low[N],dfn[N],belong[N],minx[N],maxx[N],sta[N],stop = 1; //tarjan组件
bool instack[N];
int top[N],si = 0,in[N]; //top排序组件
int mincost[N],maxcost[N],dp[N]; //动态规划组件
int node[N]; //原点值
void dfs(int now){
t++;
low[now] = dfn[now] = t;
instack[now] = true;
sta[++stop] = now;
for(edge *e = v[now];e;e=e->next)
if(!dfn[e->e]){
dfs(e->e);
low[now] = min(low[now],low[e->e]);
}
else if(instack[e->e])low[now] = min(low[now],dfn[e->e]);
if(dfn[now] == low[now]){
cnt++;
int miz = 123456789,mx = -1;
while(sta[stop] != now){
int j = sta[stop--];
belong[j] = cnt;
instack[j] = false;
miz = min(miz,node[j]);
mx = max(mx,node[j]);
}
stop--;
instack[now] = false;
belong[now] = cnt;
miz = min(miz,node[now]);
mx = max(mx,node[now]);
minx[cnt] = miz;
maxx[cnt] = mx;
maxcost[cnt] = mx-miz;
}
}
int tarjan(){
for(int a = 1; a <= n; a++) //tarjan主过程
if(!dfn[a])dfs(a);
for(int a = 1; a <= n; a++) //缩点
for(edge *e = v[a];e;e=e->next)
if(belong[a] != belong[e->e])
add_edge1(belong[a],belong[e->e]);
for(int a = 1; a <= cnt; a++) //top排序
for(edge *e = v1[a];e;e=e->next)
in[e->e]++;
for(int a = 1; a<= cnt; a++)
if(in[a] == 0)top[++si] = a;
for(int a = 1; a <= si; a++){
int now = top[a];
for(edge *e = v1[now];e;e=e->next){
in[e->e]--;
if(!in[e->e])top[++si] = e->e;
}
}
mincost[top[1]] = minx[top[1]]; //动态规划
for(int a = 1; a <= cnt; a++){
int now = top[a];
for(edge *e = v1[now];e;e=e->next){
mincost[e->e] = min(mincost[now],min(minx[e->e],mincost[now]));
dp[e->e] = max(max(dp[e->e],dp[now]),max(maxcost[e->e],maxx[e->e]-mincost[e->e]));
}
}
return dp[belong[n]];
}
int main(){
int m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)scanf("%d",&node[i]);
for(int i = 1; i <= m; i++){
int u,v,k;
scanf("%d%d%d",&u,&v,&k);
add_edge(u,v);
if(k == 2)add_edge(v,u);
}
int ans = tarjan();
printf("%d\n",ans);
return 0;
}