题解 P1073 【最优贸易】
这题的题解真是群魔乱舞
最高赞可以被卡成平方级，还有一群惨遭hack（那个男人！）
这里提供一份理论复杂度能过，思维难度小，虽然代码长了点但大多是跑板子，写起来很爽，能通过所有hack数据，在隔壁loj也能满分通过的程序。
思路是这样：
对于一个强连通分量，毫无疑问我们可以在里面自由穿梭，不干扰结果，于是我们就处理当前分量的最大和最小金钱。对于不同强联通分量，我们只要记录fi为分量i在遍历时所曾经遇到（包括自己）的最小金钱，用分量最大减去，再打擂即可。
这里有个问题，就是要求必须从起点开始回到终点，这也是大量题解被hack的原因，直接找入度为0的点是不行的！因此我们在缩点时如果遇到了1和n，就要相应地把他们的分量号标记为real1和realn，再通过一次dfs，把每一个节点标记好。
当然，对于新的图，再转移时我们必须保证所有前驱都已经完成计算，所以要先跑拓扑。
那么算法步骤如下：
1、缩点，记录每个分量的最值maxval,minval，起点终点所在分量real1,realn
2、拓扑排序，记录拓扑序列
3、从real1->realn，作一次遍历，用数组if1,ifn记录当前分量能否从起点来、到达终点
4、按照拓扑序列转移，对于可行边x,v,ans=max(ans,maxval[x]-f[x]);对于v，f[v]=min(minval[v],f[pre]);
5、同时，每个可行分量，都要内部相减记录。
总复杂度为tarjan的复杂度n+m。
码风极度清新的代码如下：
#include <bits/stdc++.h>
using namespace std;
struct line{int fr,to,data,next;}q[300001];
const int maxn=150000,INF=1000001;
int head[maxn],kl,n,x,y,z,m,ans,b[maxn],top,mon[maxn],f[maxn],ind[maxn],beg,vis[maxn];
int stac[maxn],dfn[maxn],low[maxn],indec,maxcol,col[maxn],maxval[maxn],minval[maxn];
int filo[maxn],c[maxn],bo[maxn],ifn[maxn],realn,real1,if1[maxn],g[maxn];
void pushline(int f,int t)
{
ind[t]++;
q[++kl].next=head[f];head[f]=kl;q[kl].to=t;q[kl].fr=f;
}
void tarjan(int x)
{
stac[++top]=x;
b[x]=1;
dfn[x]=low[x]=++indec;
for(int p=head[x];p;p=q[p].next)
{
int v=q[p].to;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(b[v])low[x]=min(low[x],low[v]);
}
if(dfn[x]==low[x])
{
++maxcol;
while(stac[top]!=x)
{
int u=stac[top];
if(u==n)realn=maxcol;
if(u==1)real1=maxcol;记录起终点所在分量
b[u]=0;col[u]=maxcol;
minval[maxcol]=min(minval[maxcol],mon[u]);
maxval[maxcol]=max(maxval[maxcol],mon[u]);记录分量最值
top--;
}
b[x]=0;col[x]=maxcol;
if(x==n)realn=maxcol;
if(x==1)real1=maxcol;
minval[maxcol]=min(minval[maxcol],mon[x]);
maxval[maxcol]=max(maxval[maxcol],mon[x]);
top--;
}
}
void topsort()
{
int num=0;
while(top!=0)
{
int x=filo[top--];
c[++num]=x;跑板子，记录序列
for(int p=head[x];p;p=q[p].next)
{
int v=q[p].to;
if(bo[v])continue;
ind[v]--;
if(ind[v]==0)filo[++top]=v;
}
}
}
bool dfs(int x)
{
if(vis[x])return g[x];如果当前点到过，用记搜思想直接返回即可，否则会T
vis[x]=1;
if1[x]=1;因为从真实起点开始，于是只要到过就标记
if(x==realn){ifn[x]=1;g[x]=1;}如果到达真实重点，记录，但不能直接返回，后面的点也要遍历
for(int p=head[x];p;p=q[p].next)
{
int v=q[p].to;
if(dfs(v)==1){ifn[x]=1;g[x]=1;}只要有一个儿子能到达终点，当前点也可以到
}
return g[x];
}
int main()
{
// freopen("trade3.in","r",stdin);
// freopen("trade3.out","w",stdout);
cin>>n>>m;
memset(minval,127/3,sizeof(minval));
for(int i=1;i<=n;i++)cin>>mon[i];
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
pushline(x,y);
if(z==2)pushline(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
memset(head,0,sizeof(head));
memset(ind,0,sizeof(ind));
memset(f,127/3,sizeof(f));
m=kl;
for(int i=1;i<=m;i++)
{
int x=col[q[i].fr],y=col[q[i].to];
if(x!=y)pushline(x,y);
}重新建图
top=0;
for(int i=1;i<=maxcol;i++)
{
if(ind[i]==0)filo[++top]=i,bo[i]=1;先把所有入度为0的点塞进去，bo为拓扑排序所用数组
}
topsort();
dfs(real1);记录是否可行
for(int i=1;i<=maxcol;i++)
{
int x=c[i];
if(!ifn[x]||!if1[x])continue;不符合要求就叉出去
ans=max(ans,maxval[x]-minval[x]);记录本分量内部结果
f[x]=min(f[x],minval[x]);所有的前驱都已经遍历，直接可以用
ans=max(ans,maxval[x]-f[x]);记录答案
for(int p=head[x];p;p=q[p].next)
{
int v=q[p].to;
f[v]=min(f[v],f[x]);刷表法转移
}
}
cout<<ans;
}