题解 P1073 【最优贸易】

Skyo · 2018-06-13 15:45:16 · 题解

以前在别的OJ上做过这个题, 都忘了
最近有人问起我, 找来代码, 并看不明白为什么A了
交到luogu上也A了, 哪位有缘人帮我瞧瞧, 正确性何在..?

普通的两次dfs
第一次正向, 求出minv[i], 表示从1走到i路经的最小值
第二次逆向, 求出maxv[i], 表示从i走到n路经的最大值

然后循环一遍求出max{maxv[i]-minv[i]}

总觉得有什么反例能推翻这个做法..

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

vector <int> G[100005], fG[100005]; 
int maxn[100005], minv[100005], v[100005];
int n, m;
bool vis[100005];

void init(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", v+i);
    for(int i = 1; i <= m; i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        G[x].push_back(y);
        fG[y].push_back(x);
        if(z > 1) G[y].push_back(x), fG[x].push_back(y);    
    }
}

void dfs1(int now){
    vis[now] = 1;
    for(int i = 0; i < G[now].size(); i++){
        int nex = G[now][i];
        if(vis[nex]) continue;
        minv[nex] = min(minv[now], v[nex]);
        dfs1(nex);
    }
}

void dfs2(int now){
    vis[now] = 1;
    for(int i = 0; i < fG[now].size(); i++){
        int nex = fG[now][i];
        if(vis[nex]) continue;
        maxn[nex] = max(maxn[now], v[nex]);
        dfs2(nex);
    }
}

void solve(){
    memset(minv, 0x3f, sizeof minv);
    minv[1] = v[1];
    dfs1(1);
    memset(vis, 0, sizeof vis);
    dfs2(n);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = max(ans, maxn[i] - minv[i]);
    printf("%d", ans);  
}

int main(){
    init();
    solve();
    return 0;
}