题解 P1073 【最优贸易】

· · 题解

某些时候还是要相信自己。

这题明显（对于我来说），一看就是tarjan缩点，至于后面怎么处理还没想好，于是我就写了。写完缩点后，发现有一丝迷茫，后面貌似不太好处理，然后看了看讨论，发现都是什么dfs，两遍SPFA。然后发现貌似没有tarjan缩点的做法，于是乎我开始想这道题怎么用SPFA做，可是呢，我就是放不下原来的做法，于是想了想，发现需要topo_sort一下，然后DP即可，然后就没有然后了。可见一定要相信自己！

分析：

这道题因为有的点它能（被）经过好几次，所以我们可以很容易想到：同一个强连通分量里的点可以互相到达，换言之，就是能来回走无数次。那么我们就可以用tarjan缩点，然后重新建图，对于每个新的图中的点，我们可以维护一下它的max_w和min_w和(max_w - min_w)，然后拓扑排序一下，这样做是因为我们可以找到缩点后的这个DAG上的点被经过的顺序，显然我们得先买再卖，这样也为后面的DP打下了基础。

这道题的DP就比较简单了，f[i]表示到了i点（新图）的可以赚到的最多钱数，然后我们在维护一个经过的所有点中w值最小的，就可以用minco[i]来表示。那么minco[i]=min(minco[i],minco[i的father],min_w[i])，f[i]=max(f[i],f[i的father],(max_w[i]-min_w[i]),max_w[i]-minco[i])

然后这道题就结束了，是不是特别弱智。。。

代码：

#include <bits/stdc++.h>

#define REP(i, n) for(int i = 1; i <= n; i ++)
#define REPG(i, x) for(int i = head[x]; i; i = g[i].nxt)

#define mem(x, y) memset(x, y, sizeof(x));

using namespace std;

typedef long long LL;
typedef double DB;

LL Max(LL a, LL b){return a > b ? a : b;}
LL Min(LL a, LL b){return a < b ? a : b;}

const int MAXN = 1e5 + 15;
const int MAXM = 1e6 + 15;

struct Edge{int to, nxt;}g[MAXM], e[MAXN];
int head[MAXN], cnt = 0, w[MAXN], dfn[MAXN], low[MAXN], sta[MAXN], tot = 0, tmp = 0, st, en, hh[MAXN], orzcfz = 0;
int head_sd[MAXN], cnt_sd = 0, w_sd_max[MAXN], w_sd_min[MAXN], belong[MAXN], n, m, ans = 0, in[MAXN];
int maxco[MAXN], minco[MAXN], f[MAXN], mm[MAXN], cnt_cfz = 0;
bool instack[MAXN];
queue <int> q;
void add(int u, int v){g[++ cnt] = (Edge){v, head[u]}; head[u] = cnt;}
void add_sd(int u, int v){e[++ cnt_sd] = (Edge){v, head_sd[u]}; head_sd[u] = cnt_sd;}
void add_edge(int u, int v){add(u, v); add(v, u);}

inline int read(){
    int r = 0, z = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar();}
    return r * z;
}

void fre(){
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}

void tarjan(int u){
    dfn[u] = low[u] = ++ tmp; sta[++ tot] = u; instack[u] = 1;
    for(int i = head[u]; i; i = g[i].nxt){
        int v = g[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instack[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        ans ++;
        while(sta[tot] != u){
            int gg = sta[tot]; tot --;
            instack[gg] = 0; belong[gg] = ans;
        }
        tot --; instack[u] = 0; belong[u] = ans;
    }
}

void DP(){
    memset(minco, 0x3f, sizeof(minco));
    minco[hh[1]] = w_sd_min[hh[1]];
    for(int i = 1; i <= n; i ++){
        int x = hh[i];
        for(int j = head_sd[x]; j; j = e[j].nxt){
            int y = e[j].to;
            minco[y] = min(minco[y], min(minco[x], w_sd_min[x]));
            f[y] = max(f[y], max(f[x], max(mm[y], w_sd_max[y] - minco[y])));
        }
    }
    printf("%d\n", f[en]);
}

void topo(){
    for(int i = 1; i <= ans; i ++) if(!in[i]){q.push(i); hh[++ cnt_cfz] = i;}
    while(!q.empty()){
        int u = q.front(); q.pop(); hh[++ orzcfz] = u;
        for(int i = head_sd[u]; i; i = e[i].nxt){
            int v = e[i].to;
            in[v] --;
            if(!in[v]) q.push(v);
        }
    }
    DP();
}

void suodian(){
    for(int i = 1; i <= n; i ++) if(!belong[i]) belong[i] = ++ ans;
    for(int i = 1; i <= n; i ++){
        int u1 = belong[i];
        for(int j = head[i]; j; j = g[j].nxt){
            int v1 = belong[g[j].to];
            if(u1 != v1){add_sd(u1, v1); in[v1] ++;}
        }
    }
    for(int i = 1; i <= n; i ++){
        w_sd_max[belong[i]] = max(w_sd_max[belong[i]], w[i]);
        w_sd_min[belong[i]] = min(w_sd_min[belong[i]], w[i]);
    }
    for(int i = 1; i <= ans; i ++) mm[i] = w_sd_max[i] - w_sd_min[i];
    st = belong[1], en = belong[n];
    topo();
}

void solve(){
    for(int i = 1; i <= n; i ++){
        if(!dfn[i]) tarjan(i);
    }
    suodian();
}

void init(){
    n = read(), m = read();
    memset(w_sd_min, 0x3f, sizeof(w_sd_min));
    for(int i = 1; i <= n; i ++) w[i] = read();
    for(int i = 1; i <= m; i ++){
        int u = read(), v = read(), z = read();
        if(z == 1) add(u, v);
        else add_edge(u, v);
    }
    solve();
}

int main(){
    //fre();
    init();
    return 0;
}