题解 P1073 【最优贸易】

ACalgorithm · 2018-07-16 17:59:09 · 题解

~~ 看到这个题，第一反应就是找最大和最小，但是又要在可到终点的路径上，这个就很麻烦了。。。
像我这样什么都不会的蒟蒻，就只能想到无所不能的暴力大法。~~

思路：看到题目很容易想到利用最大子段和的思想求解
步骤：1、dfs1：反向建边，标记直接或间接到达终点的边
（即通过这些边的点能走到终点，不能到达终点的边不用遍历）

void dfs1(int now){
    for(int i=head0[now];i;i=edge0[i].nt){
        if(vis[i]) continue;vis[i]=1;
        dfs1(edge0[i].to);
    }
}

     2、dfs2：正向建边，从起点遍历能到达终点的边，利用最大子段和的思想求出最大差值（即为最多能赚取的旅费）  

void dfs(int u){
    for(int i=head[u];i;i=edge[i].nt){
        if(!vis[i]) continue;vis[i]=0;
        int v=edge[i].to;
        dp[v]=max(dp[v],dp[u]+p[v]-p[u]); 
        ans=max(ans,dp[v]);dfs(v);
    }
    return ;
}

AC的原理：1、dfs2中访问的点都是能到终点的点，所以能直接求最大差值；
         2、我们只要走过所有能走边即可保证求出的差值是最大差值；
时间复杂度：就是两个dfs图，稳稳的AC 用时: 148ms / 内存: 6761KB
完整代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,vis[1000001],head[100001],p[100001],dp[100001],ans,k,k0,head0[100001];
struct node{
    int to,nt;
} edge[1000001],edge0[1000001];
void add(int u,int v){
    edge[++k].nt=head[u];
    edge[k].to=v;head[u]=k;
}
void add0(int u,int v){
    edge0[++k0].nt=head0[u];
    edge0[k0].to=v;head0[u]=k0;
}
void dfs1(int now){
    for(int i=head0[now];i;i=edge0[i].nt){
        if(vis[i]) continue;vis[i]=1;
        dfs1(edge0[i].to);
    }
}
void dfs(int u){
    for(int i=head[u];i;i=edge[i].nt){
        if(!vis[i]) continue;vis[i]=0;
        int v=edge[i].to;
        dp[v]=max(dp[v],dp[u]+p[v]-p[u]); 
        ans=max(ans,dp[v]);dfs(v);
    }
    return ;
}
int main(){
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&p[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b),add0(b,a);
        if(c==2) add(b,a),add0(a,b);
    }
    dfs1(n);dfs(1);
    printf("%d\n",ans);
    return 0;
}