P1073 最优贸易 DFS

· · 题解

题目传送门

cnblog宣传

题意：n个城市，m条边（单向或双向）

　　　每个城市对于水晶球有一个价格（买的价格与卖的价格相等）

　　　现在从1走到n，可重复经过城市，

　　　问能赚到的最大差价（在最小的地方买，最大的地方卖，且只进行一次买卖）

　　　输入边a, b, c表示a到b有(c=1 单向 c=2双向)​边

题解:

在这里提供一种只用到DFS的算法

题目可以转化为在图中找两个点权差值最大的点

这两个点要保证从1到n遍历时先遍历到点权小的点，再遍历到点权大的点。

设maxl[i]代表从i到终点能到的最大的点

设minl[i]代表从起点到i能走到的最小的点

正向建图DFS求minl

反向建图DFS求maxl

最后ans = max^n_{i=1}(maxl[i]-minl[i])

注：在建图时，采用的是一种比较特别的方式。

将所有的边建成双向边。

其中给不同的边附上不同的权值。

正向边边权附1，反向边边权附2。

双向边边权附3。

在DFS时进行判断次边是否可走即可

code:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5;
int ans, z, n, m, cnt;
int head[N], to[M], nxt[M], maxl[N], minl[N], vis[N], tag[M];
void add(int u, int v, int t) {
    to[++ cnt] = v;
    tag[cnt] = t;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
void dfs1(int x, int v) {
    if(vis[x] == 1) return;
    vis[x] = 1;
    minl[x] = min(minl[x], v);
    for(int i = head[x]; i ;i = nxt[i]) {
        int v = to[i];
        if(vis[v] == 1||tag[i] == 2) continue;
        dfs1(v, minl[x]);
    }
}
void dfs2(int x, int v) {
    if(vis[x] == 1) return;
    vis[x] = 1;
    maxl[x] = max(maxl[x], v);
    for(int i = head[x]; i ;i = nxt[i]) {
        int v = to[i];
        if(vis[v] == 1 || tag[i] == 1) continue;
        dfs2(v, maxl[x]);
    }
    ans = max(ans, maxl[x] - minl[x]);
}
int main() {
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> minl[i], maxl[i] = minl[i];
    for(int i = 1, x, y;i <= m;i ++) {
        cin >> x >> y >> z;
        if(z == 1) add(x, y, 1), add(y, x, 2);
        if(z == 2) add(x, y, 3), add(y, x, 3);
    }
    dfs1(1, minl[1]);
    memset(vis, 0, sizeof(vis));
    dfs2(n, maxl[n]);
    cout << ans << endl;
    return 0;
}