NOIP2009最优贸易(两遍SPFA/tarjan缩点+拓扑序dp)

传送门

本来想做一下tarjan缩点再拓扑序dp的题。

突然发现原来做过的这道可以用这种方法解决(原来是两遍SPFA)。

那么就合着一起总结一下吧!

原来一眼看到这道题,咦这不是水题嘛。

直接bfs一下找出能够达到1和n的点,然后这些点的max - min就好了呀!

然后愉快地敲好了代码,交上去全wa。

NOIP2009最优贸易(两遍SPFA/tarjan缩点+拓扑序dp)
#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。

NOIP2009最优贸易(两遍SPFA/tarjan缩点+拓扑序dp)
#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的连通块。用数组标记一下即可。

NOIP2009最优贸易(两遍SPFA/tarjan缩点+拓扑序dp)
#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

 

上一篇:HZOI20190725 B 回家 tarjan


下一篇:Pytorch 3 Liner Regression