【洛谷 P1073】 最优贸易 （Tarjan缩点+拓扑排序）

题目链接

先\(Tarjan\)缩点，记录每个环内的最大值和最小值。

然后跑拓扑排序，\(Min[u]\)表示到\(u\)的最小值，\(ans[u]\)表示到\(u\)的答案，\(Min\)和\(ans\)都在拓扑排序中更新和传递。

最终答案就是\(ans[n]\)。

\(100\)多行敲着心累

#include <cstdio>

#include <cstring>

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

#define Close fclose(stdin);fclose(stdout);

namespace IO{

    int xjc; char ch;

    inline int read(){

        xjc = 0; ch = getchar();

        while(ch < '0' || ch > '9') ch = getchar();

        while(ch >= '0' && ch <= '9'){ xjc = xjc * 10 + ch - '0'; ch = getchar(); }

        return xjc;

    }

}using namespace IO;

inline int max(int a, int b){

    return a > b ? a : b;

}

inline int min(int a, int b){

    return a > b ? b : a;

}

const int MAXN = 100010;

const int MAXM = 500010;

struct Queue{

    int s[MAXN];

    int head, tail;

    inline void push(int x){

        s[++tail] = x;

    }

    inline int pop(){

        return s[++head];

    }

    inline int size(){

        return tail - head;

    }

}q;

struct Edge{

    int from, next, to;

};

struct Graph{

   int head[MAXN], num;

   Edge e[MAXM << 1];

   inline void Add(int from, int to){

    e[++num].to = to; e[num].from = from; e[num].next = head[from]; head[from] = num;

   }

}G, T, P;

int dfn[MAXN], low[MAXN], id, vis[MAXN], stack[MAXN], w[MAXN], top, cnt, belong[MAXN], v[MAXN];

int minw[MAXN], maxw[MAXN], now, in[MAXN], Min[MAXN], ans[MAXN];

void Tarjan(int u){

    dfn[u] = low[u] = ++id; vis[u] = 1; stack[++top] = u;

    for(int i = G.head[u]; i; i = G.e[i].next)

       if(!dfn[G.e[i].to]){

         Tarjan(G.e[i].to);

         low[u] = min(low[u], low[G.e[i].to]);

       }

       else if(vis[G.e[i].to])

         low[u] = min(low[u], dfn[G.e[i].to]);

    if(dfn[u] == low[u]){

      ++cnt;

      do{

        now = stack[top--];

        vis[now] = 0;

        belong[now] = cnt;

        minw[cnt] = min(minw[cnt], w[now]);

        maxw[cnt] = max(maxw[cnt], w[now]);

        P.Add(cnt, now);

      }while(now != u);

    }

}

int n, m, a, b, c;

int main(){

    Open("trade");

    memset(minw, 127, sizeof minw);

    memset(Min, 127, sizeof Min);

    n = read(); m = read();

    for(int i = 1; i <= n; ++i)

       w[i] = read();

    for(int i = 1; i <= m; ++i){

       a = read(); b = read(); c = read();

       G.Add(a, b);

       if(c == 2) G.Add(b, a);

    }

    for(int i = 1; i <= n; ++i)

       if(!dfn[i])

         Tarjan(i);

    for(int i = 1; i <= cnt; ++i){

       for(int j = P.head[i]; j; j = P.e[j].next){

          int u = P.e[j].to;

          for(int k = G.head[u]; k; k = G.e[k].next)

             if(belong[G.e[k].to] != i && !v[belong[G.e[k].to]]){

               v[belong[G.e[k].to]] = 1;

               T.Add(i, belong[G.e[k].to]);

               ++in[belong[G.e[k].to]];

             }

       }

       for(int j = P.head[i]; j; j = P.e[j].next){

          int u = P.e[j].to;

          for(int k = G.head[u]; k; k = G.e[k].next)

             v[belong[G.e[k].to]] = 0;

       }

    }

    q.push(belong[1]);

    while(q.size()){

      now = q.pop();

      Min[now] = min(Min[now], minw[now]);

      ans[now] = max(ans[now], maxw[now] - Min[now]);

      for(int i = T.head[now]; i; i = T.e[i].next){

         int v = T.e[i].to;

         if(!(--in[v])) q.push(v);

         Min[v] = min(Min[v], Min[now]);

         ans[v] = max(ans[v], ans[now]);

      }

    }

    printf("%d\n", ans[belong[n]]);

    return 0;

}

【洛谷 P1073】 最优贸易 （Tarjan缩点+拓扑排序）的相关教程结束。