NOIP2009 最优贸易

不算很难的题,但是有很多细节,也有多种解法.

洛谷P1073 最优贸易

思路1 Tarjan缩点+动态规划

很明显,一个强连通分量中,可以自由来往,买入与卖出商品.在不同的强连通分量中,只有当\(i\)拓扑序严格小于\(j\)时,才能在\(j\)卖掉在\(i\)买入的物品,基于此,我们可以在缩点之后的 DAG 图上 DP .设\(DP[i]\)表示从\(1...i\)能购买到的价格最低的商品,\(Max[i]\)表示在\(i\)点所在的强连通分量内能卖出的最高价,每到一个点就转移\(DP[]\),并且用\(Max[i]-DP[i]\)更新答案.

需要注意的是,题目要求从 1 走到 n ,所以要仅从 1 开始跑一次 Tarjan,以去掉 1 出发到达不了的点.同时还要在反图中从 n 开始跑一次 DFS 标记出哪些点可以走到 n .否则会造成答案的错误.在经过了上面的处理后,原图中不是每一条边都能加入缩点后的图,可能某些点已经被去掉了,因此在重新建图的时候要特判是否加入该边.

#include<bits/stdc++.h>
const int N_MAX=100005,M_MAX=1000005,INF=0x3F3F3F3F;
int n,m,head[N_MAX],nex[M_MAX],to[M_MAX],Tot;
int P[N_MAX],DFN[N_MAX],Low[N_MAX],Sta[N_MAX],Top;

struct Graph
{
    int head[N_MAX],nex[M_MAX],to[M_MAX],Tot;
    void Link(int u,int v){nex[++Tot]=head[u];head[u]=Tot;to[Tot]=v;}
}G1,G2,G2_v;

int Cnt,B[N_MAX],Max[N_MAX],Min[N_MAX],Tim;
bool InSta[N_MAX],mk[M_MAX],Vis[N_MAX];
void Tarjan(int u)
{
    DFN[u]=Low[u]=++Tim;
    Sta[++Top]=u;
    InSta[u]=1;
    for(int i=G1.head[u];i;i=G1.nex[i])
    {
        int v=G1.to[i];
        mk[i]=1;
        if(!DFN[v])
        {
            Tarjan(v);
            Low[u]=std::min(Low[u],Low[v]);
        }
        else 
            if(InSta[v])
                Low[u]=std::min(Low[u],DFN[v]);
    }
    if(DFN[u]==Low[u])
    {
        ++Cnt;
        Max[Cnt]=-INF;
        Min[Cnt]=INF;
        do
        {
            InSta[Sta[Top]]=0;
            B[Sta[Top]]=Cnt;
            Max[Cnt]=std::max(Max[Cnt],P[Sta[Top]]);
            Min[Cnt]=std::min(Min[Cnt],P[Sta[Top]]);
        }while(Sta[Top--]!=u);
    }
}

void DFS(int u)
{
    if(Vis[u])return;
    Vis[u]=1;
    for(int i=G2_v.head[u];i;i=G2_v.nex[i])
    {
        int v=G2_v.to[i];
        DFS(v);
    }
}

std::queue<int>q;
int dp_Min[N_MAX],InD[N_MAX],Ans;
void Topo()
{
    for(int i=1;i<=Cnt;i++)
    {
        dp_Min[i]=Min[i];
        if(InD[i]==0)
        {
            q.push(i);
            Ans=std::max(Ans,Max[i]-Min[i]);
        }
    }
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(int i=G2.head[u];i;i=G2.nex[i])
        {
            int v=G2.to[i];
            dp_Min[v]=std::min(dp_Min[u],dp_Min[v]);
            --InD[v];
            if(InD[v]==0)
            {
                if(Vis[v])Ans=std::max(Ans,Max[v]-dp_Min[v]);
                q.push(v);
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&P[i]);
    int u,v,e;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&e);
        if(e==1)
            G1.Link(u,v);
        else
        {
            G1.Link(u,v);
            G1.Link(v,u);
        }
    }
    Tarjan(1);
    for(int k=1;k<=n;k++)
    {
        if(B[k]==0)continue;
        for(int i=G1.head[k];i;i=G1.nex[i])
        {
            int v=G1.to[i];
            if(B[v]==0)continue;
            if(B[k]!=B[v]&&mk[i])
            {
                G2.Link(B[k],B[v]);
                G2_v.Link(B[v],B[k]);
                InD[B[v]]++;
            }       
        }
    }
    DFS(B[n]);
    Topo();
    printf("%d",Ans);
    return 0;
}

思路2 分层图+最短路

题目的整个过程可以分为 3 层:

• 买入前
• 买入后,卖出前
• 卖出后

我们可以建立分层图,同层内部边权为 0 ,第一层到第二层的相同点之间连边,边权为该点商品价格的相反数,即"买入的花费".第二层到第三层的相同点之间连边,边权为该点商品价格,即"卖出的收益".从第一层的 1 点到第三层的 n 点跑一次最短路即可.

思路\(3...\infin\) 其他算法

比如题解中的记忆化搜索等.

NOIP2009 最优贸易

原文：https://www.cnblogs.com/TaylorSwift13/p/11774933.html