luogu P1073 最优贸易

题面传送门 因为只有一次贸易，所以可以枚举中转点。 从点$1$出发跑最小值$SPFA$，从点$n$出发跑最大值$SPFA$，这个贪心应该都懂。 然后枚举中转点，注意跑不到的点不能枚举。 代码实现:

#include<cstdio> #include<cstring> #include<queue> #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; int n,m,k,x,y,z,anss,now,tots,cur,ans[100039],dfn[100039],low[100039],vis[100039],st[100039],sh,d1[100039],d2[100039],w[100039],in[100039],maxn[100039],minn[100039]; struct yyy{int to,z;}tmp; struct ljb{ int head,h[100039]; yyy f[1000039]; inline void add(int x,int y){ f[++head]=(yyy){y,h[x]}; h[x]=head; } }s1,s2,s3; inline void tarjan(int x){ dfn[x]=low[x]=++now; vis[x]=1; st[++sh]=x; int cur=s1.h[x]; yyy tmp; while(cur!=-1){ tmp=s1.f[cur]; if(!dfn[tmp.to]) tarjan(tmp.to),low[x]=min(low[x],low[tmp.to]); else if(vis[tmp.to])low[x]=min(low[x],low[tmp.to]); cur=tmp.z; } if(dfn[x]==low[x]){ ++tots; while(st[sh+1]!=x){ vis[st[sh]]=0; ans[st[sh]]=tots; maxn[tots]=max(maxn[tots],w[st[sh]]); minn[tots]=min(minn[tots],w[st[sh]]); sh--; } } } queue<int > q; int main(){ //freopen("1.in","r",stdin); register int i; memset(s1.h,-1,sizeof(s1.h)); memset(s2.h,-1,sizeof(s2.h)); memset(s3.h,-1,sizeof(s3.h)); memset(minn,0x3f,sizeof(minn)); memset(d1,0x3f,sizeof(d1)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&w[i]); for(i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); s1.add(x,y); if(z==2) s1.add(y,x); } for(i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(i=1;i<=n;i++){ cur=s1.h[i]; while(cur!=-1){ tmp=s1.f[cur]; if(ans[i]!=ans[tmp.to]) s2.add(ans[i],ans[tmp.to]),s3.add(ans[tmp.to],ans[i]); cur=tmp.z; } } q.push(ans[1]); d1[ans[1]]=minn[ans[1]]; while(!q.empty()){ now=q.front(); q.pop(); cur=s2.h[now]; while(cur!=-1){ tmp=s2.f[cur]; if(d1[tmp.to]>d1[now]) d1[tmp.to]=min(d1[now],minn[tmp.to]),q.push(tmp.to); cur=tmp.z; } } d2[ans[n]]=maxn[ans[n]]; q.push(ans[n]); while(!q.empty()){ now=q.front(); q.pop(); cur=s3.h[now]; while(cur!=-1){ tmp=s3.f[cur]; if(d2[tmp.to]<d2[now]) d2[tmp.to]=max(d2[now],maxn[tmp.to]),q.push(tmp.to); cur=tmp.z; } } for(i=1;i<=tots;i++) anss=max(anss,d2[i]-d1[i]); printf("%d\n",anss); }