标签：答案 ace front show for inf string 最优 add
因为这道题只能买卖一次，所以我们可以用dp的思想去分段，也就是以某个位置i作为分段点
从1-i能找到的最小值和从n-i能找到最大值，答案就是差值，因为两者没有约束。这样可以包含所有情况，虽然要重复。
问题是如何求去，因为本题有环，所以我们不能真的dp求，而dp其实就是dag的最x路，因此我们可以想到用最长路和最短路来求取
这种想法可以用spfa实现，不太适合用迪杰斯特拉，因为第一次出队不一定是最小的，这不是传统的最短路，只是想求取路上的最值
本题建反图来求取最大值，因为如果正着求，最大值不一定是正确的，因为有可能最大值这条路到不了终点，而我们必须要到终点
#include
#include
#include
#include
#include
#include#define x first
#define y second
using namespace std;
typedef pairint,int> pll;
const int N=1e5+10;
const int M=2e6+10;
const int inf=0x3f3f3f3f;
int hl[M],hr[M],ne[M],e[M],w[N],idx;
int st[N];
int n,m;
int dmin[N],dmax[N];
void add(int h[],int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void spfa(int h[],int dis[],int op){
queueint> q;
if(op==0){
memset(dis,0x3f,sizeof dmin);
dis[1]=w[1];
q.push(1);
}
else{
memset(dis,-0x3f,sizeof dmax);
dis[n]=w[n];
q.push(n);
}
while(q.size()){
int t=q.front();
q.pop();
int i;
if(st[t])
st[t]=0;
for(i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(op==0){
if(dis[j]>min(dis[t],w[j])){// w[j] is for the first time to update himself
dis[j]=min(dis[t],w[j]);
if(!st[j]){
q.push(j);
st[j]=1;
}
}
}
else{
if(dis[j]// w[j] is for the first time to update himself
dis[j]=max(dis[t],w[j]);
if(!st[j]){
q.push(j);
st[j]=1;
}
}
}
}
}
}
int main(){
cin>>n>>m;
int i,j;
memset(hl,-1,sizeof hl);
memset(hr,-1,sizeof hr);
for(i=1;i){
scanf("%d",&w[i]);
}
for(i=1;i){
int a,b;
int op;
scanf("%d%d%d",&a,&b,&op);
add(hl,a,b),add(hr,b,a);
if(op==2)
add(hl,b,a),add(hr,a,b);
}
spfa(hl,dmin,0);
spfa(hr,dmax,1);
int ans=0;
for(i=1;i){
ans=max(ans,dmax[i]-dmin[i]);
}
coutendl;
}
View Code
AcWing341 最优贸易（spfa+dp思想）
标签：答案 ace front show for inf string 最优 add
原文地址：https://www.cnblogs.com/ctyakwf/p/12822044.html