题解：P1073 [NOIP2009 提高组] 最优贸易

· · 题解

P1073 [NOIP2009 提高组] 最优贸易

原题传送门

更好的阅读体验

解题思路

可以考虑分层图。

什么是分层图，顾名思义，就是有很多层的图，可以用来解决一些能使边权改变的题。

以本题举例。我们可以在任意一个城市进行买入和卖出操作，设现在在 i 号城市，买入操作对答案的贡献就是 -a_i，卖出操作对答案的贡献就是 a_i，不买不卖就是 0。

此时，我们可以建三层图，分别代表没买没卖，买了但没卖，买了也卖了。每层内的点互相连边，层与层之间对应点互相连边。层内的点互相连边的边权为 0，第一层连向第二层的边边权为 -a_i，第二层连向第三层的边边权为 a_i。答案就是第一层的 1 号点到第三层的 n 号点间的最长路。

注意事项

  1. 本题的建图方式比较特殊，第一层的编号就是原编号，第二层的编号是原编号加 n，第三层的编号是原编号加 2\times n，具体请参见代码。
  2. 本题存在负权边，需要用 spfa 跑最长路。
  3. 不要忘记将 dis 数组初始化为最小值。

参考代码

#include<iostream>
#include<queue>
#include<cstring> 
#define id(x,y) (x+y*n)//x号点在第y层的编号
using namespace std;
const int N=3e5+5,M=3e6+5;
int n,m,tot;
int a[N],dis[N],head[N];
bool vis[N];
queue<int> q;
struct Edge{
    int nxt,to,w;
}edge[M];
void add(int x,int y,int w){
    edge[++tot]={head[x],y,w};
    head[x]=tot;
}
void spfa(int s){
    memset(dis,128,sizeof(dis));//赋初值
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int t=q.front();
        q.pop();
        vis[t]=0;
        for(int i=head[t];i;i=edge[i].nxt){
            int j=edge[i].to;
            if(dis[j]<edge[i].w+dis[t]){
                dis[j]=edge[i].w+dis[t];
                if(!vis[j]){
                    q.push(j);
                    vis[j]=1;
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(id(i,0),id(i,1),-a[i]);//第一层向第二层连边
        add(id(i,1),id(i,2),a[i]);//第二层向第三层连边
    }
    for(int i=1,x,y,op;i<=m;i++){
        cin>>x>>y>>op;
        if(op==1)
            for(int j=0;j<=2;j++) add(id(x,j),id(y,j),0);//单向边
        else if(op==2)
            for(int j=0;j<=2;j++) add(id(x,j),id(y,j),0),add(id(y,j),id(x,j),0);//双向边
    }
    spfa(1);
    cout<<(dis[3*n]<0?0:dis[3*n]);
    return 0;
}

AC 记录

最后再推荐几个分层图的题，P2939，P4568，P4822，感兴趣的可以去做一下。