本来想做一下tarjan缩点再拓扑序dp的题。
突然发现原来做过的这道可以用这种方法解决（原来是两遍SPFA）。
那么就合着一起总结一下吧！
原来一眼看到这道题，咦这不是水题嘛。
直接bfs一下找出能够达到1和n的点，然后这些点的max - min就好了呀！
然后愉快地敲好了代码，交上去全wa。
#include<bits/stdc++.h>
#define LL long long
#define N 100003
#define M 500003
#define INF 2100000000
using namespace std;
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
void print(int x)
{
if(x<0)x=-x,putchar('-');
if(x>10)print(x/10);
putchar(x%10+'0');
}
struct EDEG{
int nextt,to;
}w[M*2],w2[M*2];
int head[N],head2[N],val[N];
int vis[N],vis2[N];
int tot=0,tot2=0;
int n,m;
void add(int a,int b)
{
tot++;
w[tot].nextt=head[a];
w[tot].to=b;
head[a]=tot;
}
void add_b(int a,int b)
{
tot2++;
w2[tot2].nextt=head2[a];
w2[tot2].to=b;
head2[a]=tot2;
}
queue<int>q;
void bfs(int x)
{
while(!q.empty())q.pop();
vis[x]=1;
q.push(x);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=w[i].nextt)
{
int v=w[i].to;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
void bfs_b(int x)
{
while(!q.empty())q.pop();
vis2[x]=1;
q.push(x);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head2[x];i;i=w2[i].nextt)
{
int v=w2[i].to;
if(!vis2[v])vis2[v]=1,q.push(v);
}
}
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)val[i]=read();
for(int i=1;i<=m;++i)
{
int a=read(),b=read();
int op=read();
if(op==1)
{
add(a,b);
add_b(b,a);
}
else if(op==2)
{
add(a,b);add(b,a);
add_b(a,b);add_b(b,a);
}
}
bfs(1);bfs_b(n);
int maxx=-INF,minn=INF;
for(int i=1;i<=n;++i)
{
if(vis[i]&&vis2[i])
{
maxx=max(maxx,val[i]);
minn=min(minn,val[i]);
}
}
printf("%d\n",maxx-minn);
错误代码
为什么是错的？因为我们要保证先到买入点再到卖出点。
下面看正解：
1.两遍SPFA
容易想到定义两个数组：
d[i]表示从1到这个点的最小买入值。
f[i]表示从n到这个点的最大卖出值。
然后每个点的f[i]-d[i]取个max即可。
正反SPFA各来一次就可以处理出f和d。
#include<bits/stdc++.h>
#define LL long long
#define N 100003
#define M 500003
#define INF 2100000000
using namespace std;
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
void print(int x)
{
if(x<0)x=-x,putchar('-');
if(x>10)print(x/10);
putchar(x%10+'0');
}
struct EDEG{
int nextt,to;
}w[M*2],w2[M*2];
int head[N],head2[N],val[N];
int vis[N],vis2[N],d[N],f[N];
int tot=0,tot2=0;
int n,m;
void add(int a,int b)
{
tot++;
w[tot].nextt=head[a];
w[tot].to=b;
head[a]=tot;
}
void add_b(int a,int b)
{
tot2++;
w2[tot2].nextt=head2[a];
w2[tot2].to=b;
head2[a]=tot2;
}
queue<int>q;
void SPFA(int u)//最短路
{
while(!q.empty())q.pop();
for(int i=1;i<=n;++i)
{
vis[i]=0;d[i]=INF;
}
d[u]=val[u];
vis[u]=1;
q.push(u);
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=0;
for(int i=head[x];i;i=w[i].nextt)
{
int v=w[i].to;
if(d[v]>min(d[x],val[v]))
{
d[v]=min(d[x],val[v]);
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
}
void SPFA_b(int u)
{
while(!q.empty())q.pop();
for(int i=1;i<=n;++i)
{
vis2[i]=0;f[i]=-INF;
}
f[u]=val[u];
vis2[u]=1;
q.push(u);
while(!q.empty())
{
int x=q.front();q.pop();vis2[x]=0;
for(int i=head2[x];i;i=w2[i].nextt)
{
int v=w2[i].to;
if(f[v]<max(f[x],val[v]))
{
f[v]=max(f[x],val[v]);
if(!vis2[v])
{
vis2[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)val[i]=read();
for(int i=1;i<=m;++i)
{
int a=read(),b=read();
int op=read();
if(op==1)
{
add(a,b);
add_b(b,a);
}
else if(op==2)
{
add(a,b);add(b,a);
add_b(a,b);add_b(b,a);
}
}
SPFA(1);SPFA_b(n);
int ans=-INF;
for(int i=1;i<=n;++i)
ans=max(ans,f[i]-d[i]);
printf("%d\n",ans);
}
/*
*/
SPFA
tarjan缩点+拓扑序dp
图中可能有环，所以我们会自然地想到缩点。
缩点之后变成一个DAG，于是我们根据拓扑序dp一下即可。
注意可能有到不了n的连通块。用数组标记一下即可。
#include<bits/stdc++.h>
#define LL long long
#define N 100003
#define M 500003
#define INF 2100000000
using namespace std;
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
void print(int x)
{
if(x<0)x=-x,putchar('-');
if(x>10)print(x/10);
putchar(x%10+'0');
}
struct edge{
int x,y;
}e[M*2];
struct EDEG{
int nextt,to;
}w[M*2];
int head[N],val[N];
int d[N],f[N];
int tot=0;
int n,m;
void add(int a,int b)
{
tot++;
w[tot].nextt=head[a];
w[tot].to=b;
head[a]=tot;
}
int vis[N],low[N],dfn[N],stackk[N];
int maxx[N],minn[N],reach[N],in[N],ans[N],bel[N];
int timer=0,cnt=0,top=0;
void tarjan(int x)
{
dfn[x]=low[x]=++timer;
vis[x]=1;stackk[++top]=x;
for(int i=head[x];i;i=w[i].nextt)
{
int v=w[i].to;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x])
{
cnt++;
maxx[cnt]=-INF;minn[cnt]=INF;
int t;
do{
t=stackk[top--];
maxx[cnt]=max(maxx[cnt],val[t]);
minn[cnt]=min(minn[cnt],val[t]);
vis[t]=0;
bel[t]=cnt;
}while(x!=t);
}
}
queue<int>q;
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)val[i]=read();
int num=0;
for(int i=1;i<=m;++i)
{
int a=read(),b=read();
int op=read();
if(op==1)
{
add(a,b);
e[++num].x=a;e[num].y=b;
}
else if(op==2)
{
add(a,b);add(b,a);
e[++num].x=a;e[num].y=b;
e[++num].x=b;e[num].y=a;
}
}
for(int i=1;i<=n;++i)
if(!dfn[i])tarjan(i);
memset(head,0,sizeof(head));
tot=0;
for(int i=1;i<=num;++i)
{
int a=e[i].x,b=e[i].y;
if(bel[a]==bel[b])continue;
add(bel[a],bel[b]);
in[bel[b]]++;
}
reach[bel[1]]=1;
while(!q.empty())q.pop();
for(int i=1;i<=cnt;++i)
if(!in[i])q.push(i);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=w[i].nextt)
{
int v=w[i].to;
if(reach[x])//要考虑到那些无法到达n的连通块
{
reach[v]=1;
ans[v]=max(ans[v],ans[x]);
minn[v]=min(minn[v],minn[x]);
ans[v]=max(ans[v],maxx[v]-minn[v]);
//ans[i]表示在i这里卖出，所以maxx不与前面取max
//但买入是可以更小的
}
in[v]--;
if(!in[v])q.push(v);
}
}
printf("%d",ans[bel[n]]);
}
/*
*/
tarjan+拓扑dp