【洛谷P1073】[NOIP2009]最优贸易

最优贸易

题目链接

看题解后感觉分层图好像非常NB巧妙

建三层n个点的图，每层图对应的边相连，权值为0

即从一个城市到另一个城市，不进行交易的收益为0

第一层的点连向第二层对应的点的边权为-w[i],表示买入的收益

第二层的点连向第三层对应的点的边权为w[i],表示卖出的收益

这样跑一遍最长路，就可以了

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

#define N 300030

#define M 1200030

int n,m,dis[N],tot,Head[N];

queue<int> q;

bool inque[N];

struct NODE{

    int to,next,w;

} e[M];

inline int read(){

    int x=; char c=getchar();

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

    return x;

}

inline void add(int x,int y,int w){

    e[++tot].to=y;

    e[tot].w=w;

    e[tot].next=Head[x];

    Head[x]=tot;

}

inline void unionn(int x,int y){

    add(x,y,);

    add(x+n,y+n,);

    add(x+n+n,y+n+n,);

}

int main()

{

    n=read(); m=read();

    int x,y,z;

    for(int i=;i<=n;i++){

        x=read();

        add(i,i+n,-x);

        add(i+n,i+n+n,x);

    }

    add(n,n+n+n+,);

    for(int i=;i<=m;i++){

        x=read(); y=read(); z=read();

        unionn(x,y);

        if(z==) unionn(y,x);

    }

    add(n+n+n,n+n+n+,);

    memset(dis,-,sizeof(dis));

    q.push(); dis[]=;

    while(!q.empty()){

        int u=q.front(); q.pop();

        inque[u]=;

        for(int i=Head[u];i;i=e[i].next){

            int v=e[i].to;

            if(dis[v]<dis[u]+e[i].w){

                dis[v]=dis[u]+e[i].w;

                if(!inque[v]){

                    inque[v]=;

                    q.push(v);

                }

            }

        }

    }

    printf("%d\n",dis[n+n+n+]);

    return ;

}