[NOIP2009 提高组] 最优贸易

方法一 ：分层图

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
const int N = 1e5+10,M = 3e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;int n,q,m;int e[M],ne[M],w[M],h[3*N],idx;
void add(int a,int b,int c){e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
}int cost[N];
int dist[N];
bool vis[N];void spfa()
{queue<int>q;q.push(1);memset(dist,-0x3f,sizeof dist);dist[1] = 0;vis[1] = true;while(q.size()){auto t = q.front();q.pop();vis[t] = false;for(int i=h[t];~i;i=ne[i]){int j = e[i];if(dist[j]<dist[t]+w[i]){dist[j] = dist[t]+w[i];if(!vis[j])q.push(j);}}}cout<<dist[n*3];
}void solve()
{cin>>n>>m;memset(h,-1,sizeof h);for(int i=1;i<=n;i++){cin>>cost[i];;add(i,i+n,-cost[i]);add(i+n,i+n+n,cost[i]);}while(m--){int a,b,op;cin>>a>>b>>op;add(a,b,0),add(a+n,b+n,0),add(a+n+n,b+n+n,0);if(op==2){add(b,a,0),add(b+n,a+n,0),add(b+n+n,a+n+n,0);			}}spfa();}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;//cin>>_;_ = 1;while(_--)solve();return 0;
}

方法二：spfa图上DP  用minn存储从1号点开始到达i点为之能搞到的最小花费，maxn表示从i号点到n号点的最大价值

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
#define int long long
const int N = 5e5+10,M = 2e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;int n,q,m;int cost[N];
int dmin[N],dmax[N];
bool vis[N];
int e[M],ne[M],w[M],h[N],hs[N],idx;
void add(int h[],int a,int b){e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}void spfa(int h[],int dist[],int type)
{queue<int>q;memset(vis,0,sizeof vis);if(!type){memset(dist,0x3f,4*N);dist[1] = cost[1];vis[1] = true;q.push(1);}else{memset(dist,-0x3f,4*N);dist[n] = cost[n];vis[n] = true;q.push(n);}while(q.size()){auto t = q.front();q.pop();vis[t] = false;for(int i=h[t];~i;i=ne[i]){int j = e[i];if((type==0&&dist[j]>min(dist[t],cost[j]))||(type==1&&dist[j]<max(dist[t],cost[j]))){if(!type)dist[j] = min(dist[t],cost[j]);if(type)dist[j] = max(dist[t],cost[j]);if(!vis[j]){q.push(j);vis[j] = false;}}}}}void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>cost[i];memset(h,-1,sizeof h),memset(hs,-1,sizeof hs);for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(h,a,b),add(hs,b,a);if(c==2)add(h,b,a),add(hs,a,b);}spfa(h,dmin,0);spfa(hs,dmax,1);int ans = 0;for(int i=1;i<=n;i++)ans = max(ans,dmax[i]-dmin[i]);cout<<ans;}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;//cin>>_;_ = 1;while(_--)solve();return 0;
}