【最优贸易】

孤叶残影 · 2019-09-20 12:59:58 · 题解

分层图+dijkstra

有人用分层图+SPFA，但出题人卡你的话，你就只有凉凉了，那么我用dijkstra就比较保险，但DIJKSTRA只能跑最短路，那么就将花钱记成正数，卖出记成负数，最后比相反值；

分三层，第一层只旅游不买不卖，第二层在当前点买，第三层在当前点卖；

#include<bits/stdc++.h>
using namespace std;
const int N = 100050;
const int M = 500050;
int head[M*3],cnt,n,m;
bool vis[N*3];
struct Edge{
    int to;
    int w;
    int next;
}edge[M*3];
int dist[N*3];
void add(int x,int y,int d)
{
    cnt++;
    edge[cnt].next = head[x];
    edge[cnt].to = y;
    edge[cnt].w = d;
    head[x] = cnt;
} 
struct node{
    int pos;
    int dist;
    bool operator <(const node& that)const{
    return dist > that.dist;
    }
};
int su[N];
priority_queue<node> q;
void djs()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    q.push((node){1,0});
    while(!q.empty())
    {
        int x = q.top().pos;q.pop();
        for(int i = head[x];i;i = edge[i].next)
        {
            int y = edge[i].to;
            if(dist[y]>dist[x]+edge[i].w)
            {
                //cout<<"en"<<endl;
                dist[y]=dist[x]+edge[i].w;
                q.push((node){y,dist[y]});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    cin>>su[i];
    for(int i = 1;i <= m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;//开始建图
        if(c==1)
        {
            for(int j = 0;j < 3;j++)
            {
                add(a+j*n,b+j*n,0);//不买卖
            }
            add(a,b+n,su[a]);//买入
            add(a+n,b+n+n,-su[a]);//卖出
        }
        else
        {
            for(int j = 0;j < 3;j++)
            {
                add(a+j*n,b+j*n,0);//双向建边
                add(b+j*n,a+j*n,0);
            }
            add(a,b+n,su[a]);
            add(b,a+n,su[b]);
            add(a+n,b+n+n,-su[a]);
            add(b+n,a+n+n,-su[b]);
        }//当然保险起见可以再在n点与3*n点连一条权值0的边
    }
    djs();
    int ans=0;
    ans=max(ans,-dist[n*3]);
    cout<<ans<<endl;
    return 0;
}

分层图还有几个可称为模板的紫题，如，都是紫题就这一道是蓝题