(Zerojudge) d779: NOIP2009 3.最优贸易

https://zerojudge.tw/ShowProblem?problemid=d779

我是先想50%，之後才想到100%的！

在寫50%的時候，我發現圖是一個DAG，用DAG來維護一些東西。

那在推廣到100%的時候，我就在想，要怎麼把整張圖推廣到DAG --> SCC！

50%的版本：

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 1e5 +6;

vector<int> edg[MAX_N];
int a[MAX_N];
int mn[MAX_N];
int mxans[MAX_N];
int deg[MAX_N];

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++) {
        scanf("%d",&a[i]);
        mn[i] = a[i];
        mxans[i]=0;
    }
    for (int i=0;m>i;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        if (c==1) edg[a].push_back(b);
        else {
            edg[a].push_back(b);
            edg[b].push_back(a);
        }
        deg[b]++;
    }
    int ans=0;
    queue<int> que;
    que.push(1);
    while (!que.empty()) {
        int t=que.front();
        que.pop();
        mxans[t] = max(mxans[t],a[t]-mn[t]);
        for (int i:edg[t]) {
            mn[i] = min(mn[i],mn[t]);
            deg[i]--;
            mxans[i] = max(mxans[i],mxans[t]);
            if (deg[i]==0) que.push(i);
        }
    }
    printf("%d\n",mxans[n]);
}

100%的版本：

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX_N = 1e5 + 6;
const int INF = 1e9 + 7;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
vector<int> scc_edg[MAX_N];
int scc_mx[MAX_N],scc_mn[MAX_N],scc_ans[MAX_N];
int a[MAX_N];
bool visit[MAX_N];
int get_stamp[MAX_N];
int in_scc[MAX_N];
int ansmx[MAX_N];
int deg[MAX_N];

void gao1(int id,int &stamp) {
    visit[id]=1;
    for (int i:rev_edg[id]) {
        if (!visit[i]) {
            gao1(i,stamp);
        }
    }
    get_stamp[stamp++]=id;
}

void gao2(int id,int scc) {
    visit[id]=1;
    for (int i:edg[id]) {
        if (!visit[i]) {
            gao2(i,scc);
        }
    }
    in_scc[id]=scc;
    scc_mx[scc] = max(scc_mx[scc],a[id]);
    scc_mn[scc] = min(scc_mn[scc],a[id]);
}

int build_scc(int n) {
    memset(visit,0,sizeof(visit));
    int stamp=1;
    for (int i=1;n>=i;i++) {
        if (!visit[i]) {
            gao1(i,stamp);
        }
    }
    fill(scc_mx,scc_mx+MAX_N,-INF);
    fill(scc_mn,scc_mn+MAX_N,INF);
    memset(visit,0,sizeof(visit));
    int scc=0;
    for (int i=n;i>=1;i--) {
        if (!visit[get_stamp[i]]) {
            gao2(get_stamp[i],++scc);
        }
    }
    for (int i=1;n>=i;i++) {
        for (int j:edg[i]) {
            if (in_scc[i] != in_scc[j]) {
//                cout<<"build edge i = "<<in_scc[i]<<" , j = "<<in_scc[j]<<endl;
                scc_edg[in_scc[i]].push_back(in_scc[j]);
            }
        }
    }
    return scc;
}

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++) {
        scanf("%d",&a[i]);
    }
    for (int i=1;m>=i;i++) {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        edg[a].push_back(b);
        rev_edg[b].push_back(a);
        if (c==2) {
            edg[b].push_back(a);
            rev_edg[a].push_back(b);
        }
    }
    int scc=build_scc(n);
//    cout<<"scc = "<<scc<<endl;
//    for (int i=1;n>=i;i++) {
//        cout<<"in_scc["<<i<<"] = "<<in_scc[i]<<endl;
//    }
    queue<int> que;
    for (int i=1;scc>=i;i++) {
        for (int j:scc_edg[i]) {
            deg[j]++;
        }
    }
    que.push(in_scc[1]);
    while (!que.empty()) {
        int t=que.front();
//        cout<<"T = "<<t<<endl;
        que.pop();
        ansmx[t] = max(ansmx[t],scc_mx[t]-scc_mn[t]);
        for (int i:scc_edg[t]) {
            deg[i]--;
            scc_mn[i] = min(scc_mn[i],scc_mn[t]);
            ansmx[i] = max(ansmx[i],ansmx[t]);
            if (deg[i] == 0) que.push(i);
        }
    }
    printf("%d\n",ansmx[in_scc[n]]);
}