P1073 最优贸易


似乎题解里都是两遍spfa,加堆优化的dijkstra也能过,这道题其实求出两个点a b要b-a最大,而且b的遍历顺序要在a后面,可以考虑两次dijkstra来维护d与v两数组处理,d表示走到这个节点前面能买到的最便宜的货,f表示这个节点往后走最大可以卖出多少钱,当然这算是广义的dijkstra,其实是用它来维护一个动态规划
$$
\begin{cases}
d[v]=min(d[u],w[v])\
f[v]=max(f[u],w[v])
\end{cases}
$$
d在正向图跑,同时建一个反向边图跑f,这样就可以保证a点一定在b之前,这样对于一个每点算出$f[i]-d[i]$后取最大值即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
typedef pair<int,int> p;
int head1[maxn],num1=0,num2=0,head2[maxn];
int n,m,wi[maxn];
int f[maxn],d[maxn];
int vis[maxn];
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
struct node{
    int v,w,nex;
}e1[maxn],e2[maxn];
void add1(int u,int v,int w)
{
    e1[++num1].v=v;
    e1[num1].w=wi[v];
    e1[num1].nex=head1[u];
    head1[u]=num1;
}
void add2(int u,int v,int w)
{
    e2[++num2].v=v;
    e2[num2].w=wi[v];
    e2[num2].nex=head2[u];
    head2[u]=num2;
}
void dij1()
{
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    priority_queue<p,vector<p>,greater<p> > q1;
    d[1]=wi[1];
    q1.push(make_pair(wi[1],1));
    while(!q1.empty())
    {
        int u=q1.top().second;
        q1.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head1[u];i;i=e1[i].nex)
        {
            int v=e1[i].v;
            d[v]=min(d[u],wi[v]);
            q1.push(make_pair(d[v],v));
        }
    }
}
void dij2()
{
    memset(f,-0x3f,sizeof(f));
    memset(vis,0,sizeof(vis));
    priority_queue<p,vector<p>,greater<p> > q2;
    f[n]=wi[n];
    q2.push(make_pair(wi[n],n));
    while(!q2.empty())
    {
        int u=q2.top().second;
        q2.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head2[u];i;i=e2[i].nex)
        {
            int v=e2[i].v;
            f[v]=max(f[u],wi[v]);
            q2.push(make_pair(f[v],v));
        }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) wi[i]=read();
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read(),y=read(),z=read();
        if(z==1) add1(x,y,z),add2(y,x,z);
        else add1(x,y,z),add1(y,x,z),add2(x,y,z),add2(y,x,z);
    }
    dij1();
    dij2();
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i]-d[i]);
    printf("%d\n",ans);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
CF1196 CF1196
A. Three Piles of Candies题解:答案为$\lfloor \frac{a+b+c}{2} \rfloor$ #include<cstdio> #include<algorithm> #include<
2019-07-29
下一篇 
P1438 无聊的数列 P1438 无聊的数列
区间加等差数列模板,维护a的差分数组c,对于$l-r$的首项为k公差为d的等差数列,只要对c进行3个操作$c[l]+k$ , $c[l+1-r]+d$ , $c[r+1]-(k+(r-l)*d)$,直接线段树维护c的区间加 区间查询即可,注
2019-07-06
  目录