NOIP2009 最优贸易

题目:

  C国有n个大城市和m条道路,每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为1条。
  C国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。
  商人阿龙来到C国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后,便决定在旅游的同时,利用商品在不同城市中的差价赚回一点旅费。设C国n个城市的标号从1-n,阿龙决定从1号城市出发,并最终在n号城市结束自己的旅行。在旅游的过程中,任何城市可以重复经过多次,但不要求经过所有n个城市。阿龙通过这样的贸易方式赚取旅费:他会选择一个经过的城市迈入他最喜欢的商品——水晶球,并在之后经过的另一个城市卖出这个水晶球。用赚取的差价当作旅费。由于阿龙主要是来C国旅游,他决定这个贸易只进行最多一次。当然,在赚不到差价的情况下它就无需进行贸易。
  现在给出n个城市的水晶球价格,m条道路的信息(每条道路所连接的两个城市的编号以及该条道路的通行情况)。请你告诉阿龙,他最多能赚钱多少旅费。

思路:

  • 最短路解法一:
      最短路跑出从1到每个点水晶球的最小值,枚举在哪个点卖,再判断下卖的点能不能走到终点就行了。
  • 最短路解法二:
      建一副三层的图,第一层到第二层代表买水晶球,第二层到第三层代表卖水晶球。每层之间按照题目建图,然后直接跑最短路就行了。
      ps:觉得解法二更灵活,如果路上要花路费也能很好的解决。这种建图貌似叫分层图,感觉可以解决一些不单要走路,还有一些操作的问题。
  • 缩点:
      缩点后在DAG上处理问题,记录每个块的最小/大值,设代表从出发,到点路径上的最小值。每次用更新答案即可。

代码:

  • 最短路解法一:
#include <bits/stdc++.h>
#define MAXN 100005
#define inf 105
#define tomax(a,b) a<(b)?a=(b):a
using namespace std;
int dis[MAXN],cost[MAXN],n;
bool inq[MAXN],pd[MAXN];
vector<int> fmp[MAXN],mp[MAXN];
void bfs(){
    queue<int> q;
    q.push(n);
    pd[n]=true;
    while(!q.empty()){
        int o=q.front();
        q.pop();
        for(int i=0;i<fmp[o].size();i++)
            if(!pd[fmp[o][i]]){
                q.push(fmp[o][i]);
                pd[fmp[o][i]]=true;
            }
    }
}
void spfa(){
    deque<int> q;
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    q.push_front(1);
    inq[1]=true;
    dis[1]=cost[1];
    while(!q.empty()){
        int o=q.front();
        inq[o]=false;
        q.pop_front();
        for(int i=0;i<mp[o].size();i++){
            int v=mp[o][i];
            //cout<<dis[v]<<' '<<dis[o]<<endl;
            if(dis[v]>min(dis[o],cost[v])){
                dis[v]=min(dis[o],cost[v]);
                if(!inq[v]){
                    if(q.empty()||dis[v]>dis[q.front()])
                        q.push_front(v);
                    else
                        q.push_back(v);
                }
                inq[v]=true;
            }
        }

    }
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",cost+i);
    for(int i=1,a,b,c;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        mp[a].push_back(b);
        fmp[b].push_back(a);
        if(c==2){
            mp[b].push_back(a);
            fmp[a].push_back(b);
        }
    }
    bfs();spfa();
    int ans=0;
    for(int i=1;i<=n;i++)
        if(pd[i])
            tomax(ans,cost[i]-dis[i]);
    printf("%d",ans);
    return 0;
}
  • 最短路解法二:
#include <bits/stdc++.h>
#define MAXN 300015
#define inf 200
using namespace std;
struct Edge{
    int w,to;
};
vector<Edge> mp[MAXN];
int dis[MAXN],n;
bool inq[MAXN];
void addEdge(int a,int b){
    mp[a].push_back((Edge){0,b});
    mp[a+n].push_back((Edge){0,b+n});
    mp[a+n+n].push_back((Edge){0,b+n+n});
}
void spfa(){
    deque<int> q;
    for(int i=n*3;i;i--)
        dis[i]=-inf;
    dis[1]=0;inq[1]=true;
    q.push_front(1);
    while(!q.empty()){
        int o=q.front();
        q.pop_front();
        inq[o]=false;
        for(int i=0;i<mp[o].size();i++){
            int u=mp[o][i].to,l=mp[o][i].w;
            if(dis[u]<dis[o]+l){
                dis[u]=dis[o]+l;
                if(!inq[u]){
                    inq[u]=true;
                    if(q.empty()||dis[q.front()]<dis[u])
                        q.push_front(u);
                    else
                        q.push_back(u);
                }
            }
        }
    }
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1,c;i<=n;i++){
        scanf("%d",&c);
        mp[i].push_back((Edge){-c,i+n});
        mp[i+n].push_back((Edge){c,i+n+n});
    }
    for(int i=1,a,b,c;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        addEdge(a,b);
        if(c==2)
            addEdge(b,a);
    }
    spfa();
    printf("%d",dis[n*3]==-inf?0:dis[n*3]);
    return 0;
}
  • 缩点:
#include <bits/stdc++.h>
#define MN 100005
#define clr(a,b) memset(a,b,sizeof a)
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
Link<MN,1000005,int> F,G,M;
int dfn[MN],low[MN],ble[MN],stk[MN],tp,No,bcnt,Min[MN],Max[MN],val[MN];
void dfs(int o){
    dfn[o]=low[o]=++No;
    stk[++tp]=o;
    EOR(k,G,o){
        int v=G[k];
        if(!dfn[v]){
            dfs(v);
            tomin(low[o],low[v]);
        }
        else if(!ble[v])tomin(low[o],dfn[v]);
    }
    if(dfn[o]==low[o]){
        bcnt++;
        do {
            ble[stk[tp]]=bcnt;
            tomin(Min[bcnt],val[stk[tp]]);
            tomax(Max[bcnt],val[stk[tp]]);
        }while(stk[tp--]!=o);
    }
}
int n,ind[MN];
void rebuild(){
    FOR(o,1,n)EOR(k,G,o){
        int v=G[k];
        if(ble[v]!=ble[o]){
            M.add(ble[o],ble[v]);
            F.add(ble[v],ble[o]);
//            cout<<"DEBUG:"<<ble[v]<<' '<<ble[o]<<endl;
            ind[ble[v]]++;
        }
    }
}
bool ok1[MN],ok2[MN];
void bfs(){
    queue<int> q;
    ok1[ble[n]]=1;q.push(ble[n]);
    while(!q.empty()){
        int v=q.front();q.pop();
        EOR(k,F,v){
            int x=F[k];
            if(!ok1[x])q.push(x);
            ok1[x]=1;
        }
    }
    ok2[ble[1]]=1;q.push(ble[1]);
    while(!q.empty()){
        int v=q.front();q.pop();
        EOR(k,M,v){
            int x=M[k];
            if(!ok2[x])q.push(x);
            ok2[x]=1;
        }
    }
}
int dp[MN],q[MN];
int Dp(){
    int hed=1,tai=0,ans=0;
    FOR(i,1,bcnt){
        if(!ind[i])q[++tai]=i;
        dp[i]=Min[i];
    }
    while(hed<=tai){
        int v=q[hed++];
        if(ok1[v]&&ok2[v])tomax(ans,Max[v]-dp[v]);
        EOR(k,M,v){
            int x=M[k];
            if(ok2[v])tomin(dp[x],dp[v]);
            if(!--ind[x])
                q[++tai]=x;
        }
    }
    return ans;
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    FOR(i,1,n)scanf("%d",val+i);
    for(int i=1,a,b,k;i<=m;i++){
        scanf("%d%d%d",&a,&b,&k);
        G.add(a,b);
        if(k==2)G.add(b,a);
    }
    clr(Min,63);
    FOR(i,1,n)if(!dfn[i])
        dfs(i);
    rebuild();bfs();
    printf("%d\n",Dp());
    return 0;
}