圖論

題型整理：
1. 距離計算
P-7-1. 探索距離
 P-7-2. 開車蒐集寶物

BFS

注意事項！！最常出錯的地方：一定要記得宣告vis陣列
1. q.push後面會加上一個vis=true (所以共兩個)
2. 判斷if(!vis[i]){ … }
3. q是要取first

最基本寫法

void bfs(int ff){

    queue<int>q;
    bool vis[N];
    
    q.push(ff);  
    vis[ff]=true;             //vis (1/3) push 後面加上一個 vis
    
    while(!q.empty()){
        int f=q.front();q.pop();
        for(int i:v[f]){ 
            if(!vis[i]){      //vis(2/3)
                q.push(i);
                vis[i]=true;  // vis(3/3) push 後面加上一個 vis

                cout<<i;      // 所有的點一定會被放入一次，所以在這處理要做的動作
            
            }
        }
    }
}

廣度優先，可以看成洪水擴散
深藍是離開佇列的節點
淺藍是走到的點
綠色是加入佇列的點

alt text

步驟：
1. 首先將第一個點加入佇列
2. 接著走到第一個點（也就是佇列的第一個），將其子節點依序放入佇列
3. 刪除佇列中第一個點

重複2~3直到佇列沒有東西(沒有下一個點)

實作

在資料結構的部分我們需要：
1. 存路徑的vector
2. 存是否拜訪的陣列
3. 一個queue儲存拜訪順序

以上面的圖解為例

輸入：
第一行為節點數、路徑數（m）
第二行為起點
接下來有m行，為不同路徑

輸出：

1 2 3 4 5 6

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000
vector<int>v[N];

void bfs(int ff){
    queue<int>q;
    bool vis[N];
    q.push(ff);
    vis[ff]=true;             //vis (1/3)
    while(!q.empty()){
        int f=q.front();q.pop();
        for(int i:v[f]){ 
            if(!vis[i]){      //vis(2/3)
                vis[i]=true;  // vis(3/3)
                q.push(i);
                cout<<i;
            }
        }
    }
}

signed main(){
    istringstream cin("7 6 \
0 \
0 1 \
0 2 \
1 3 \
1 4 \
4 5 \
4 6");//123456
    int n,m;
    cin>>n>>m;
    int f;
    cin>>f;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }
    bfs(f);
}

Danger | 注意！！！

有三處需要 vis
vis在雙向圖、邊的起點與終點未必不同時必須加上

P-7-1. 探索距離

https://judge.tcirc.tw/ShowProblem?problemid=d090

P-7-1. 探索距離
輸入一個有向圖 G 與一個起點 s，請計算由 s 出發可以到達的點數(不包含 s)，並且計算這些可以到達的點與 s 的距離和，假設每個邊的長度均為 1。兩點之間可能有多個邊，邊的起點與終點未必不同。

Time limit: 1 秒

輸入格式：
第一行是兩個正整數 n 與 m，代表圖的點數與邊數，圖的點是以 0~n-1 編號，第二行是 s 的編號，接下來有 m 行，每一行兩個整數 a 與 b 代表一個邊(a,b)。n 不超過 100，m 不超過 4000。

輸出：
第一行輸出可以到達的點數，第二行輸出與 s 的距離總和。

範例輸入：
7 6
1
5 1
1 3
1 4
2 3
4 6
6 0

範例輸出：
4
7

這題比較困難的部分是如何計算高度

我們可以知道「子節點的高度」為「父節點的高度」+1
所以dp[子]=dp[父]+1

另外，這題不能用DFS，因為這是圖不是樹，最短距離要用BFS

#include<bits/stdc++.h>
using namespace std;
#define nn "\n"
#define N 101
// istream& ss=cin;
// stringstream ss(" ");



vector<int>v[N];
int ans_1=0;
int ans_2=0;
int d[N]={0};
bool vis[N]={false};


void bfs(int a){
    queue <int>q;
    q.push(a);
    vis[a]=true;  //不要忘記！！！！
    d[a]=0;
    while(!q.empty()){
        int f=q.front();
        q.pop();
        for(int i:v[f]){
            if(!vis[i]){//不要忘記！！！！
                vis[i]=true;//不要忘記！！！！
                d[i]=d[f]+1;
                ans_1++;
                ans_2+=d[i];
                q.push(i);
            }
        }
    }
}



int main(){
    int n,m,a;
    cin>>n>>m>>a;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }

    bfs(a);
    cout<<ans_1<<nn<<ans_2;
    return 0;
}

DFS

最基本寫法

void dfs(int f){
    vis[f]=true;       //標記為走過
    for(int i:v[f]){
        if(!vis[i]){   //排除走過的
            cout<<i;
            dfs(i);
        }
    }
    return;
}

能走多深就走多深，走不下去就回頭

做法：
對於每個迭代到的節點進行迭代(遞迴)

input，多加一條線4->2測vis

output

0 1 3 4 5 6 2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000
vector<int>v[N];
bool vis[N];

void dfs(int f){
    vis[f]=true;
    for(int i:v[f]){
        if(!vis[i]){
            cout<<i;
            dfs(i);
        }
    }
    return;
}

signed main(){
    istringstream cin("7 6 \
0 \
0 1 \
0 2 \
1 3 \
1 4 \
4 5 \
4 6"); //134562
    int n,m;
    cin>>n>>m;
    int f;
    cin>>f;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
    }
    dfs(f);
}

P-7-2. 開車蒐集寶物

https://judge.tcirc.tw/ShowProblem?problemid=d091

參加一個蒐集寶物的遊戲，你拿到一個地圖，地圖上有 n 個藏寶點，每個藏寶點有若干價值的寶物，由於你的團隊是最頂尖的，只要能到達藏寶點一定可以取得該藏寶點的寶藏。從地圖上看得到一共有 m 條道路，每條道路連接兩個藏寶點，而且每條道路都是雙向可以通行的。在遊戲的一開始，你可以要求直升機將你的團隊運送到某個藏
寶點，而且你可以獲得一部車與充足的油料，但是直升機的載送只有一次，所以你必須決定要從哪裡開始才可以獲得最多的寶藏總價值。

Time limit: 1 秒

輸入格式：
第一行是兩個正整數 n 與 m，代表藏寶地點數與道路數，地點是以 0~n-1 編號，第二行 n 個非負整數，依序是每一個地點的寶藏價值，每個地點的寶藏價值不超過 100。接下來有 m 行，每一行兩個整數 a 與 b 代表一個道路連接的兩個地點編號。n 不超過 5e4，m 不超過 5e5。兩點之間可能有多條道路，有些道路的兩端點可能是同一地點。

輸出：
最大可以獲得的寶藏總價值。

注意vis就好
因為有vis，所以每個點只會跑到一次。

#include <bits/stdc++.h>
using namespace std;

vector<int> w, vis;
vector<vector<int>> v;
int x, y, sum, ans;

void dfs(int f) {
    vis[f] = 1;

    sum += w[f];

    // cout << f << " ";

    for (int i : v[f]) {
        if (!vis[i]) {
            dfs(i);
        }
    }

    return;
}

int main() {
    int n, m;
    cin >> n >> m;

    v.resize(n);
    w.resize(n);
    vis.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            sum = 0;

            dfs(i);

            ans = max(ans, sum);
        }
    }

    cout << ans;

    return 0;
}

DAG 與 topological sort

DAG:
DAG(directed acyclic graph)是指一種有向沒有環的圖

topological sort(拓樸順序):
對於節點給予優先順序，像是先闖完哪一關才能到哪一關之類的

拓樸排序的方法:

找出所有in-degtee=的點放入陣列

找到queue[head]的子節點，將他們的in-degtee減一，如果變成0，放入queue，將tail往後

移動head往後

一直重複2、3直到全部找完

因為不一定是dag所以最後要檢查tail<n

alt text

input

0 6 1 2 7 4 3 5

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m,x,y;
    cin >> n >> m;

    vector<vector<int>>v(n);
    vector<int>vis(n);
    vector<int>in(n);
    
    for(int i=0;i<m;i++){
        cin>>x>>y;
        v[x].push_back(y);
        in[y]++;
    }
    
    queue<int>q;
    
    for(int i=0;i<n;i++){
        if(in[i]==0){
            q.push(i);
            vis[i]=1;
        }
    }
    
    while(!q.empty()){
        
        int f=q.front();
        q.pop();
        
        cout<<f<<" ";
        
        
        for(int i:v[f]){
            if(!vis[i]){
                in[i]--;
                if(in[i]==0){
                    q.push(i);
                    vis[i]=1;
                }
            }
        }
        
        
    }
    return 0;
}

習題

UVA-10305

https://vjudge.net/problem/UVA-10305

要選機器人帳號

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, x, y;
    while (cin >> n >> m) {
        
        if(n==0&&m==0)break;
        
        vector<vector<int>> v(n+1);
        vector<int> vis(n+1);
        vector<int> in(n+1);

        for (int i = 0; i < m; i++) {
            cin >> x >> y;
            v[x].push_back(y);
            in[y]++;
        }

        queue<int> q;

        for (int i = 1; i <=n; i++) {
            if (in[i] == 0) {
                q.push(i);
                vis[i] = 1;
            }
        }

        while (!q.empty()) {
            int f = q.front();
            q.pop();

            cout << f << " ";

            for (int i : v[f]) {
                if (!vis[i]) {
                    in[i]--;
                    if (in[i] == 0) {
                        q.push(i);
                        vis[i] = 1;
                    }
                }
            }
        }
        cout << "\n";
    }
    return 0;
}

f167. m4a1-社團 Club

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, x, y;
    cin >> n >> m;
    vector<vector<int>> v(n + 1);
    vector<int> vis(n + 1);
    vector<int> in(n + 1);
    vector<int> ans;

    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        in[y]++;
    }

    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            q.push(i);
            vis[i] = 1;
        }
    }

    while (!q.empty()) {
        int f = q.front();
        q.pop();

        ans.push_back(f);

        for (int i : v[f]) {
            if (!vis[i]) {
                in[i]--;
                if (in[i] == 0) {
                    q.push(i);
                    vis[i] = 1;
                }
            }
        }
    }

    if (ans.size() == n) {
        cout << "YES\n";
        for (int i : ans) {
            cout << i << "\n";
        }
    }
    else{
        cout<<"NO";
    }
    
    return 0;
}

a552. 模型

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

送你一個範例測資：

0 2 3 1 5 4

解1

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, x, y;
    while (cin >> n >> m) {
        vector<vector<int>> v(n);
        vector<int> vis(n);
        vector<int> in(n);

        for (int i = 0; i < m; i++) {
            cin >> x >> y;
            v[x].push_back(y);
            in[y]++;
        }

        queue<int> q;
        int found;
        while (1) {
            found = 0;
            for (int i = 0; i < n; i++) {
                if (in[i] == 0 && !vis[i]) {
                    
                    found = 1;
                    
                    vis[i] = 1;
                    cout << i << " ";

                    for (int i : v[i]) {
                        if (!vis[i]) {
                            in[i]--;
                        }
                    }
                    
                    break;  // 找到
                }
            }
            if(!found)break;
        }

        cout << "\n";
    }
    return 0;
}

解2

//  https://seanxd.com/zh/zerojudge-a552/
#include <iostream>
#include <map>
using namespace std;

map<int, map<int, int>>MAP, before;
map<int, int>walk;

void BFS(map<int, int>start) {
    map<int, int>push;
    while(start.size() > 0) {
        const auto first = *start.begin();
        start.erase(start.begin());
        const int num = first.first;
        bool ok = true;
        for (auto it:before[num]) {
            if (walk[it.first] == 0) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            push[num] = 0;
            continue;
        }
        cout << num << " ";
        walk[num]++;
        const map<int, int> mm = MAP[num];
        for (auto it:mm) {
            if (walk[it.first] == 0 && push[it.first] == 0) {
                push[it.first]++;
                start[it.first]++;
            }
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    while (cin >> N >> M) {
        walk.clear();
        MAP.clear();
        before.clear();
        map<int, int>dad;
        for (int i = 0; i<M; i++) {
            int a, b;
            cin >> a >> b;
            dad[b]++;
            before[b][a]++;
            MAP[a][b]++;
        }
        map<int, int>start;
        for (int i = 0; i<N; i++) {
            if (dad[i] == 0) {
                start[i]++;
            }
        }
        BFS(start);
        cout << "\n";
    }
}

//ZeroJudge A552
//Dr. SeanXD

m933. 3. 邏輯電路

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

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int p, q, r, m, x, y;
    cin >> p >> q >> r >> m;

    vector<int> type(p + q + r + 1);
    vector<vector<int>> input(p + q + r + 1);
    vector<int> indegree(p + q + r + 1);
    vector<vector<int>> v(p + q + r + 1);
    vector<int> output(p + q + r + 1);
    vector<int> d(p + q + r + 1);
    int maxd = 0;

    for (int i = 1; i <= p; i++) {
        cin >> x;
        input[i].push_back(x);
        output[i] = x;
    }

    for (int i = 1; i <= p; i++) {
        type[i] = -1;  // input gate
    }
    for (int i = p + 1; i <= p + q; i++) {
        cin >> type[i];
    }
    for (int i = p + q + 1; i <= p + q + r; i++) {
        type[i] = 0;  // output gate
    }

    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        indegree[y]++;
    }

    queue<int> que;

    for (int i = 1; i <= p + q + r; i++) {
        if (indegree[i] == 0) {
            que.push(i);
        }
    }

    while (!que.empty()) {
        int f = que.front();
        que.pop();

        if (type[f] == -1 || type[f] == 0) {
            output[f] = input[f][0];
        } else if (type[f] == 1) {
            if (input[f][0] && input[f][1]) {
                output[f] = 1;
            } else {
                output[f] = 0;
            }

        } else if (type[f] == 2) {
            if (input[f][0] || input[f][1]) {
                output[f] = 1;
            } else {
                output[f] = 0;
            }

        } else if (type[f] == 3) {
            if (input[f][0] ^ input[f][1]) {
                output[f] = 1;
            } else {
                output[f] = 0;
            }

        } else if (type[f] == 4) {
            output[f] = !input[f][0];
        }

        for (int i : v[f]) {
            indegree[i]--;
            input[i].push_back(output[f]);

            d[i] = max(d[i], d[f] + 1);
            maxd = max(maxd, d[i]);

            if (!indegree[i]) {
                que.push(i);
            }
        }
    }

    cout << maxd - 1 << "\n";
    for (int i = p + q + 1; i <= p + q + r; i++) {
        cout << output[i] << " ";
    }

    return 0;
}

基礎習題

d092: P-7-3. 機器人走棋盤 (APCS 201906)

https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a121

alt text

此題利用了一個技巧：int dn[4]={0,1,-1,0},dm[4]={1,0,0,-1};

#include<bits/stdc++.h>
using namespace std;
#define N 111
#define inf 2147483640
#define nn "\n"
int v[N][N];
int x,y;
int vis[N][N];
int n,m;
int ans=0;

int vv(int i,int j){
    if( (i<0 || i>=n)|| (j<0 || j>=m)    ){
        return inf;
    }
    return v[i][j];
}

int main(){
    //istringstream cin("\
4 5 \
24 7 14 20 30 \
11 6 4 21 29 \
2 8 1 35 40 \
3 9 5 12 15\
");
    //istringstream cin("2 7 \
6 8 7 2 1 4 5 \
9 3 10 11 12 13 14");
    int mi_element=inf;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>v[i][j];
            if(v[i][j]<mi_element){
                x=i;
                y=j;
                mi_element=v[i][j];
            }
        }
    }
    vis[x][y]=true;
    ans+=v[x][y];
    int ton[4]={0,1,0,-1};
    int tom[4]={1,0,-1,0};
    while(1){
        int mi=inf;
        int xx=-1,yy=-1;
        for(int i=0;i<4;i++){
            if(vv(x+ton[i],y+tom[i])<mi && !vis[x+ton[i]][y+tom[i]]){
                xx=x+ton[i];
                yy=y+tom[i];
                mi=vv(x+ton[i],y+tom[i]);
            }
        }
        if(mi==inf){
            cout<<ans;
            return 0;
        }
        x=xx;
        y=yy;
        vis[x][y]=true;
        ans+=vv(x,y);
    }
}

d093: P-7-4. 方格棋盤的最少轉彎數路線

https://judge.tcirc.tw/ShowProblem?problemid=d093

有一個 m*n 的方格棋盤，每個格子可能是 0 或 1，其中 0 代表可以通過而 1 代表不能通過。現在有一個機器人從左上角編號(1,1)的格子出發，要到達右下角編號 (m,n)的格子，每次可以往上下左右四個方向移動，我們要找到轉彎次數最少的路線。 Time limit: 1 秒

輸入格式：第一行是兩個正整數 m 與 n，代表格子棋盤的列數與行數，接下來有 m 行，每行是一個長度為 n 僅由 0 與 1 組成的字串，代表方格棋盤由上往下由左至右的內容，出發與目的格子必然是 0。m 與 n 不超過 500。

輸出：最少的轉彎數。如果無法到達，則輸出-1。

這一題可以發現他的輸入之間並沒有空格，如下：
3 6
001010
101000
100010

所以沒辦法使用數字陣列一個一個位置輸入，除非想要先字串分析

這邊使用了一個方法：
宣告為字串陣列，一列一列輸入
&vi 指的是每列開頭的指標
cin>>&vi就是將字串放入&v[i][1~n]

第35行的while (v[ti][tj] == '0')是為了一直沿著直線一走下去，每一「批」直線是一組，dis[]相同，如下圖。

alt text

#include <bits/stdc++.h>
using namespace std;
#define nn "\n"

istream &ss = cin;

// stringstream ss("3 6 001010 101000 100010");
struct st{
    int x;
    int y;
};
char v[501][501];
int dis[501][501];
int n, m;
int main(){
    ss >> n >> m;
    for (int i = 1; i <= m; i++){
        ss >> &v[i][1];
    }
    for (int i = 0; i < m + 2; i++){
        v[0][i] = '1';
        v[n + 1][i] = '1';
    }
    for (int i = 0; i < n + 2; i++){
        v[i][0] = '1';
        v[i][m + 1] = '1';
    }
    memset(dis, -1, sizeof(dis));
    // bfs
    st a = {1, 1};
    int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
    queue<st> q;
    q.push({1, 1});
    dis[1][1] = 0;
    while (!q.empty() && dis[n][m] < 0){  //走完一條直線
        int fi = q.front().x, fj = q.front().y;
        q.pop();
        for (int i = 0; i < 4; i++){
            int ti = fi + di[i], tj = fj + dj[i];
            while (v[ti][tj] == '0'){
                if (dis[ti][tj] == -1){
                    dis[ti][tj] = dis[fi][fj] + 1;
                    q.push({ti, tj});
                }
                ti = ti + di[i], tj = tj + dj[i];
            }
        }
    }
    if (dis[n][m] > 0){
        dis[n][m]--;
    }

    cout << dis[n][m];
}

d094: Q-7-5. 闖關路線 (APCS201910)

https://judge.tcirc.tw/ShowProblem?problemid=d094

某個闖關遊戲上有一隻神奇寶貝與兩個可控制左右移動的按鍵。神奇寶貝被安置在僅可左右移動的滑軌上。滑軌分成 n 個位置，由左到右分別以 0 ~ n – 1 表示。當遊戲開始時，神奇寶貝從位置 0 開始，遊戲的資訊包含 P、L 與 R 三個數字，其中 P 表示所須移至的目標位置，L 與 R 則分別表示每按一次左鍵或右鍵後，會往左或往右移動的格子數。此外，每一個位置 x 都對應一個瞬間移動位置 S(x)；每一次按鍵後，神奇寶貝會先依據按鍵往左或右移動到某個位置 x，接著瞬間移動至 S(x)。某些點的瞬間移動位置等同原地點，也就是 S(x) = x，這些點稱為停留點。開始與目標位置都一定是停留點；此外，每個點的瞬間移動位置都一定是停留點(除非超出界外)，也就是不會發生連續瞬間移動的情形。遊戲的目標是以最少的按鍵數操作神奇寶貝由開始位置到達目標位置，此外，在移動過程中不可以超過滑軌的範圍[0, n – 1]，否則算闖關失敗；某些點的瞬間移動位置也可能會超出滑軌的範圍，移動到這些點也會導致闖關失敗。

Time limit: 1 秒

輸入格式：輸入有兩行，第一行有 4 個數字，第 1 個為 n，第 2 個為目標位置 P，第 3 個為 L，第 4 個為 R，後三個數字皆為小於 n 之正整數，且 2 ≤ n ≤ 1e6。第二行有 n 個整數，依序是各點的瞬間移動位置 S(0), S(1), …, S(n – 1)，這些數字是絕對值不超過 1e8 的整數。

輸出：輸出到達目標位置所需的最少按鍵數，如果無法到達目標位置，則輸出 –1。

這題直接使用BFS，透過d來存放步數，也就是計算樹的高度。
而父節點的高度是子節點的高度+1，遞迴式：dp[子]=dp[父]+1

而左、右走之後直接「瞬移」，因為如果可以瞬移會直接瞬移，否則會停留在原地，而且
瞬移不會算是一個「移動」。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1000005;
int n, p, l, r, a[maxn], d[maxn], now, nxt;
  
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> p >> l >> r) {
        for (int i = 0; i < n; i++){
        cin >> a[i];
        if (a[i] >= n || a[i] < 0) a[i] = n;
    }
    memset(d, -1, sizeof(d));
    d[0] = 0;
    queue <int> q;
    q.push(0);
    while (!q.empty() && d[p] == -1){
        now = q.front();
        q.pop();
        nxt = now - l;
        if (nxt >= 0 && a[nxt] != n && d[a[nxt]] == -1){
            d[a[nxt]] = d[now] + 1;
            q.push(a[nxt]);
        }
        nxt = now + r;
        if (nxt < n && a[nxt] != n && d[a[nxt]] == -1){
            d[a[nxt]] = d[now] + 1;
            q.push(a[nxt]);
        }
    }
    cout << d[p] << "\n";
    }
    return 0;
}

錯誤版

#include <bits/stdc++.h>
using namespace std;
#define N 10000001
#define nn "\n"


int d[N];

int s[N];
int n,p,l,r;


bool can(int a){
    if(a<n && a>=0 && d[a]==-1){//
        return true;
    }
    return false;
}

set<int>se;


int main(){
    
    cin>>n>>p>>l>>r;

    for(int i=0;i<n;i++){
        cin>>s[i];
    }

    //bfs;

    queue<int>q;
    memset(d,-1,sizeof(d));
    
    q.push(0);
    d[0]=0;


    while(!q.empty()){
        int f=q.front();
        //cout<<"f:"<<f<<"   ";
        q.pop();

        if(f==p){
            se.insert(d[f]);
        }
        if(can(s[f])){
            d[s[f]]=d[f];
            q.push(s[f]);
            //cout<<"s[f]:"<<s[f]<<" ";
        }

        if(can(f-l)){
            d[f-l]=d[f]+1;
            q.push(f-l);

            //cout<<"l:"<<f-l<<" ";
        }

        if(can(f+r)){
            d[f+r]=d[f]+1;
            q.push(f+r);

            //cout<<"r:"<<f+r<<" ";
        }
        cout<<nn;
    }
    int c=1;
    if(!se.empty()){
        cout<<*se.rend();
        c=0;
    }
    
    if(c){
        cout<<-1;
    }
    
}

alt text

Q-7-7. AOV 最早完工時間

alt text

範例一輸入：
3 2
1 3 4
1 3
2 3
範例一輸出：
7
2 3

範例二輸入：
4 4
1 2 3 4
1 2
1 3
1 4
3 4

範例二輸出：
8
1 3 4

這題可能會有多個根如例題1的1、2（應該說有拓樸的樹，因為多個根其實可以拉成一棵樹），因此我們要依照拓樸對於每一個根看看高度，再對於每個高度取max，再將max加總。

#include<bits/stdc++.h>
using namespace std;
#define N 100001
#define nn "\n"



int w[N]={0};
vector<int>v[N];
bool vis[N]={false};
queue<int>q;
int inde[N]={0};
int h[N]={0};
vector<pair<int,int>>v_h[N];


bool cmp(pair<int,int> a , pair<int,int> b){
    return  a.second > b.second;
}

//stringstream ss("3 2 1 3 4 1 3 2 3 ");
&istream  ss= cin;

int main(){
    int  n,m;
    ss>>n>>m;//工作數量、前置關係數
    for(int i=1;i<=n;i++){
        ss>>w[i];
    }
    for(int i=0;i<m;i++){
        int x,y;
        ss>>x>>y;
        inde[y]++;
        v[x].push_back(y);
    }
    for(int i=1;i<n;i++){
        if(inde[i]==0){
            h[i]=0;
            v_h[0].push_back({i,w[i]});
            q.push(i);
        }
    }


    while(!q.empty()){
        int f=q.front();
        q.pop();
        for(int i:v[f]){
            inde[i]--;
            if(inde[i]==0){
                h[i]=h[f]+1;
                v_h[h[i]].push_back({i,w[i]});
                q.push(i);
            }
        }
    }


    cout<<nn;

    for(int i=0;i<n;i++){
        sort(v_h[i].begin(),v_h[i].end(),cmp);
    }

    int all=0;

    int w=0;
    while(v_h[w].size()){
        all+=v_h[w][0].second;
        w++;
    }
    cout<<all<<nn;

    w=0;
    while(v_h[w].size()){
        cout<<v_h[w][0].first<<" ";
        w++;
    }
}

有權重的邊

D - Transit Tree Path

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

signed main() {
    int n, x, y, z;
    cin >> n;

    vector<vector<pii>> v(n + 1);

    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y >> z;

        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }

    vector<int> dis(n + 1);
    vector<int> vis(n + 1);
    queue<int> que;

    int q, k;
    cin >> q >> k;

    que.push(k);
    vis[k] = 1;

    while (!que.empty()) {
        int f = que.front();
        que.pop();

        // cout << f;

        for (pii i : v[f]) {
            if (!vis[i.first]) {
                que.push(i.first);
                vis[i.first] = 1;

                dis[i.first] = dis[f] + i.second;
            }
        }
    }

    for (int i = 0; i < q; i++) {
        cin >> x >> y;
        cout << dis[x] + dis[y] << "\n";
    }

    return 0;
}

D - Even Relation

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

signed main() {
    int n, x, y, z;
    cin >> n;

    vector<vector<pii>> v(n + 1);

    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y >> z;

        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }

    vector<int> c(n + 1);
    vector<int> vis(n + 1);
    queue<int> que;

    que.push(1);
    vis[1] = 1;

    while (!que.empty()) {
        int f = que.front();
        que.pop();

        for (pii i : v[f]) {
            if (!vis[i.first]) {
                que.push(i.first);
                vis[i.first] = 1;

                if (i.second & 1)
                    c[i.first] = !c[f];
                else
                    c[i.first] = c[f];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << c[i] << "\n";
    }

    return 0;
}

Dijkstra 演算法用來計算一個圖中一點到其他點的最短路徑

1. 為什麼 pop 出來就能確定

Dijkstra Algorithm(Dijkstra 演算法) 解的是 Single-Source Shortest Path(單源最短路徑)：從一個起點 s 到所有點的最短距離。它要求邊權重是 non-negative(非負數)，也就是不能有負邊；這點是它正確性的核心限制。(CP Algorithms)

你可以把 Dijkstra 想成：

BFS 是每條邊成本都一樣時的最短路；Dijkstra 是每條邊成本不一樣、但都不會是負數時的 BFS。

2. 核心概念：`dist[v]` 不是答案，一開始只是「目前找到的最好答案」

我們先定義：

dist[v] = 從起點 s 到 v，目前已知的最短距離

注意，是「目前已知」，不是一開始就保證正確。

一開始：

dist[s] = 0
dist[其他點] = INF

然後每次從 Priority Queue(優先佇列) 裡面拿出 目前 dist 最小的點。

這一步是整個 Dijkstra 最重要的貪婪選擇：

目前所有還沒確定的點裡，誰的 dist 最小，就先確定誰。

3. 為什麼「最小的點」可以直接確定？

假設現在 Priority Queue 裡面最小的是點 u，距離是 dist[u]。

你可能會想：

會不會之後繞一條路，讓 u 變更短？

Dijkstra 的回答是：不會。

原因是所有邊權重都是非負數。

如果之後要找到一條更短的路到 u，那條路一定會先經過某個還沒處理的點 x，再走到 u。

可是因為 u 已經是目前距離最小的點，所以：

dist[u] <= dist[x]

而從 x 再走一些邊到 u，邊權重又不會是負數，所以距離只會增加或不變：

dist[x] + 後面的邊 >= dist[x] >= dist[u]

所以不可能比 dist[u] 更短。

這就是 Dijkstra 的核心 Invariant(不變量)：

每次從 Priority Queue 取出的最小距離點，它的最短距離就已經確定了。

4. Relaxation(鬆弛) 是什麼？

Relaxation(鬆弛) 其實就是檢查：

「如果我先到 u，再從 u 走到 v，會不會比原本到 v 的方法更短？」

公式是：

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
}

生活化例子：

你目前知道：

家 -> 學校 = 20 分鐘

現在發現：

家 -> 捷運站 = 5 分鐘
捷運站 -> 學校 = 10 分鐘

所以：

家 -> 捷運站 -> 學校 = 15 分鐘

比原本的 20 分鐘短，於是更新：

dist[學校] = 15

這就是 Relaxation(鬆弛)。

5. 流程圖

flowchart TD
    A["初始化 dist<br/>起點為 0<br/>其他為 INF"] --> B["把起點放入 Min-Heap"]
    B --> C{"Priority Queue 是否為空"}
    C -->|是| H["結束<br/>dist 就是最短距離"]
    C -->|否| D["取出目前距離最小的點 u"]
    D --> E{"這筆資料是否過期<br/>d != dist[u]"}
    E -->|是| C
    E -->|否| F["枚舉 u 的所有鄰居 v"]
    F --> G{"dist[u] + w &lt; dist[v]"}
    G -->|是| I["更新 dist[v]<br/>並把新距離丟入 Priority Queue"]
    G -->|否| F
    I --> F
    F --> C

6. 用一個小圖走一次

假設從 1 出發：

1 -> 2，成本 2
1 -> 3，成本 5
2 -> 3，成本 1
2 -> 4，成本 4
3 -> 4，成本 2

圖長這樣：

graph LR
    A((1)) -->|2| B((2))
    A -->|5| C((3))
    B -->|1| C
    B -->|4| D((4))
    C -->|2| D

初始：

dist[1] = 0
dist[2] = INF
dist[3] = INF
dist[4] = INF

7. 實際執行表

步驟	pop 出來的點	目前距離	做的事	dist 結果
1	1	0	更新 2、3	`dist[2]=2, dist[3]=5`
2	2	2	透過 2 更新 3、4	`dist[3]=3, dist[4]=6`
3	3	3	透過 3 更新 4	`dist[4]=5`
4	3	5	這是舊資料，跳過	不變
5	4	5	沒有更短路	完成

最後答案：

dist[1] = 0
dist[2] = 2
dist[3] = 3
dist[4] = 5

注意第 4 步很重要。

Priority Queue 裡可能有舊資料，例如：

一開始 1 -> 3 = 5，所以丟入 (5, 3)
後來 1 -> 2 -> 3 = 3，又丟入 (3, 3)

所以 (5, 3) 變成過期資料。

競程常見寫法是：

if (d != dist[u]) continue;

這叫 lazy deletion(懶刪除)，因為 C++ 的 priority_queue 不方便直接修改裡面舊的 key，所以我們讓舊資料留著，取出來時再跳過。CP-algorithms 也採用 Priority Queue(優先佇列) 版本來處理 sparse graph(稀疏圖) 的 Dijkstra 實作。(CP Algorithms)

8. C++ 標準模板

模板程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

int INF = 2e4;

signed main() {
    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<pii>> g(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        int w;
        cin >> u >> v >> w;

        g[u].push_back({v, w});

        // 如果是無向圖，才加這行：
        // g[v].push_back({u, w});
    }

    vector<int> dist(n + 1, INF);
    dist[s] = 0;

    priority_queue<
        pii,
        vector<pii>,
        greater<pii>
    >pq;

    pq.push({0, s});

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

        int d = cur.first;
        int u = cur.second;

        if (d != dist[u]) continue;  // 遇到比較舊比較長的路徑，直接跳過

        for (auto e : g[u]) {
            int v = e.first;
            int w = e.second;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        printf("dis[%lld] = ", i);
        if (dist[i] == INF)
            cout << "INF\n";
        else
            cout << dist[i] << "\n";
    }

    return 0;
}

輸入：

輸出：

dis[1] = 0
dis[2] = 2
dis[3] = 3
dis[4] = 5

輸出過程的程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

int INF = 2e4;

signed main() {
    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<pii>> g(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        int w;
        cin >> u >> v >> w;

        g[u].push_back({v, w});

        // 如果是無向圖，才加這行：
        // g[v].push_back({u, w});
    }

    vector<int> dist(n + 1, INF);
    dist[s] = 0;

    priority_queue<
        pii,
        vector<pii>,
        greater<pii>>
        pq;

    pq.push({0, s});
    //================================
    printf("push {0,%lld}\n", s);
    //================================

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

        int d = cur.first;
        int u = cur.second;

        //================================
        printf("pop {%lld,%lld}\n", d, u);
        //================================

        if (d != dist[u]) {  // 遇到比較舊比較長的路徑，直接跳過

            //================================
            printf("continue {%lld,%lld}\n", d, u);
            //================================

            continue;
        }

        for (auto e : g[u]) {
            int v = e.first;
            int w = e.second;

            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                //================================
                printf("dist[%lld] = %lld  ", v, dist[u] + w);
                //================================

                pq.push({dist[v], v});
                //================================
                printf("push {%lld,%lld}\n", dist[v], v);
                //================================
            }
        }
    }

    cout << "\n";

    for (int i = 1; i <= n; i++) {
        printf("dis[%lld] = ", i);
        if (dist[i] == INF)
            cout << "INF\n";
        else
            cout << dist[i] << "\n";
    }

    return 0;
}

輸出

push {0,1}
pop {0,1}
dist[2] = 2  push {2,2}
dist[3] = 5  push {5,3}
pop {2,2}
dist[3] = 3  push {3,3}
dist[4] = 6  push {6,4}
pop {3,3}
dist[4] = 5  push {5,4}
pop {5,3}
continue {5,3}
pop {5,4}
pop {6,4}
continue {6,4}

dis[1] = 0
dis[2] = 2
dis[3] = 3
dis[4] = 5

9. 你可以這樣記 Dijkstra

不要背「流程」，要背這個核心：

dist[v] = 目前找到的最短路

每次挑 dist 最小的點 u

因為邊權非負，
所以其他還沒處理的點不可能繞出更短路回來救 u

因此 u 的答案確定

然後用 u 去更新鄰居

一句話版：

Dijkstra 每次確定離起點最近的未確定點，然後用這個點去改善其他點的距離。

10. 最常見錯誤

10.1 把點 push 進 Priority Queue 時就當成確定

錯誤想法：

點 v 被 push 進 pq，所以 v 的答案確定了

這是錯的。

正確是：

點 v 從 pq pop 出來，而且它是目前最新 dist，才確定

10.2 有負邊還用 Dijkstra

如果有負邊，Dijkstra 的「pop 出來就確定」會壞掉。

例子：

1 -> 2 = 2
1 -> 3 = 5
3 -> 2 = -10

一開始看起來：

dist[2] = 2
dist[3] = 5

Dijkstra 會先確定 2。

但其實：

1 -> 3 -> 2 = -5

更短。

所以負邊要用 Bellman-Ford Algorithm(Bellman-Ford 演算法)、SPFA，或其他處理負權圖的方法。Dijkstra 標準版本的前提是 non-negative edge weights(非負邊權)。(CP Algorithms)

10.3 `priority_queue` 預設是 Max-Heap

C++ 預設：

priority_queue<int> pq;

是最大值優先。

Dijkstra 要 Min-Heap(最小堆)，所以要寫：

priority_queue<
    pair<ll, int>,
    vector<pair<ll, int>>,
    greater<pair<ll, int>>
> pq;

11. 最後用一句直覺收斂

Dijkstra 其實不是魔法。

它只是一直問：

目前我最有把握、距離最短的點是誰？

然後因為所有路都不會有負成本，所以：

更遠的點不可能繞一圈讓這個最近的點變更近

因此最近的點可以被安全確定。

你真正要抓住的是這句：

非負邊權保證：目前最小的暫定距離，未來不可能再變小。

例題

https://judge.tcirc.tw/problem/d096

P-7-9. 最短路徑 (*) 輸入一個無向圖 G=(V,E,w)，其中點以 0~n-1 編號，而邊的權重是非負整數。計算 0 號點到其他點的最短路徑長度。兩點之間可能有多個邊。 Time limit: 1 秒輸入格式：第一行是兩個正整數 n 與 m，代表點數與邊數，接下來有 m 行，每行三個整數 u, v, w 代表一條無向邊(u,v)的長度是 w。n 不超過 1e4，m 不超過 1e5, w 是不超過 1e4 的非負整數。輸出：第一行輸出 0 到各點之最短路徑長度中的最大值，也就是在可以到達的點中，最短距離最大的是多少，第二行輸出有多少點無法從抵達。

範例一輸入：
7 6
0 2 3
0 1 1
2 3 4
1 4 0
3 4 2
5 4 3

範例一輸出：
4
1

範例二輸入：
3 3
2 1 5
1 0 0
0 1 1

範例二輸出：
5
0

範例一示意圖：

alt text

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

int INF = 2e4;

signed main() {
    int n, m;
    cin >> n >> m;  // 點:0~n-1, 邊數:m

    vector<vector<pii>> v(n);
    vector<int> dis(n, INF);

    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;

        v[x].push_back({y, w});
        v[y].push_back({x, w});  // 雙向
    }

    priority_queue<
        pii,
        vector<pii>,
        greater<pii>>
        pq;  // 小到大

    pq.push({0, 0});

    //=====================
    // printf("push {0,0}\n");
    //=====================

    dis[0] = 0;

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        // =====================
        // printf("pop {%lld,%lld}\n", d, u);
        //=====================

        if (d != dis[u]) continue;

        for (pii pp : v[u]) {
            int v = pp.first;  // 這邊是從 v 拿出來的所以要是正常的順序，v 是 first，w 是 second。
            int w = pp.second;

            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});

                //=====================
                // printf("push {%lld,%lld}\n", dis[v], v);
                //=====================
            }
        }
    }

    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        if (dis[i] == INF) {
            ans2++;
        } else {
            ans1 = max(ans1, dis[i]);
        }
    }
    cout << ans1 << "\n"
         << ans2;

    return 0;
}

練習題

D - Super Takahashi Bros.

https://atcoder.jp/contests/abc340/tasks/abc340_d

Single Source Shortest Path

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

併查集

1. 併查集在解決什麼問題

Disjoint Set Union(併查集)，也常叫 Union-Find(合併查找)，專門處理這種問題：

有很多個元素，我們需要一直做兩件事：

把兩個元素所在的群組合併

查兩個元素是否在同一個群組

例如：

1 和 2 是朋友
2 和 3 是朋友
問：1 和 3 是不是同一群？

答案是：是。因為：

1 -- 2 -- 3

所以 1、2、3 屬於同一個集合。

併查集的標準做法會用 rooted tree(有根樹) 表示集合，每個集合用一個 representative(代表點)，也就是 root(根節點) 代表整群。Boost 的 disjoint_sets 文件也把這個資料結構描述為用 parent tree(父節點樹) 維護不相交集合，並搭配 path compression(路徑壓縮) 和 union by rank(依秩合併) 加速操作。(boost.org)

2. 核心原理

我們開一個陣列：

parent[i]

意思是：

i 的爸爸是 parent[i]

一開始每個人都是自己一群，所以：

parent[i] = i;

例如有 5 個點：

1  2  3  4  5

一開始：

parent[1] = 1
parent[2] = 2
parent[3] = 3
parent[4] = 4
parent[5] = 5

每個點自己就是 root(根)。

3. find_root 是什麼

find_root(x) 的目的：

找出 x 所在集合的 root(根節點)。

例如：

1 -> 2 -> 3

代表：

parent[1] = 2;
parent[2] = 3;
parent[3] = 3;

那麼：

find_root(1)

會一路往上找：

1 的爸爸是 2
2 的爸爸是 3
3 的爸爸是 3，所以 3 是 root

所以：

find_root(1) == 3

4. path compression(路徑壓縮)

如果每次都慢慢往上找，樹太高會變慢。

所以我們找 root 的時候，順便把路徑上的點直接接到 root。

原本：

1 -> 2 -> 3 -> 4

執行：

find_root(1)

之後變成：

1 -> 4
2 -> 4
3 -> 4
4 -> 4

也就是下次查 1、2、3 都會很快。

核心程式只有這樣：

int find_root(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find_root(parent[x]);
}

這行最重要：

return parent[x] = find_root(parent[x]);

它同時做兩件事：

1. 找到 root
2. 把 parent[x] 直接改成 root

5. 合併兩個集合

假設要合併 a 和 b。

錯誤想法是：

parent[a] = b;

這樣不穩，因為 a 不一定是 root。

正確做法是：

int ra = find_root(a);
int rb = find_root(b);

意思是：

ra = a 那一群的代表
rb = b 那一群的代表

如果：

ra == rb

代表它們本來就在同一群，不用合併。

如果：

ra != rb

就把其中一個 root 接到另一個 root 底下。

6. union by size(依大小合併)

我們再開一個：

sz[i]

意思是：

如果 i 是 root，sz[i] 表示這一群有幾個元素

合併時，把小集合接到大集合下面，樹會比較矮。

if (sz[ra] < sz[rb]) swap(ra, rb);

parent[rb] = ra;
sz[ra] += sz[rb];

意思是：

如果 ra 那群比較小，就交換 ra 和 rb
保證 ra 是比較大的那群
然後把 rb 接到 ra 底下

搭配 path compression(路徑壓縮) 後，併查集的操作非常接近 O(1)。較正式地說，經典分析會用 inverse Ackermann function(反阿克曼函數) 描述其成長，非常慢；Tarjan 的集合合併演算法分析就是這類複雜度的代表性來源。(OA Monitor Ireland)

7. 視覺化流程

flowchart TD
    A["輸入操作 op a b"] --> B{"op 是合併嗎？"}
    B -->|"是"| C["ra = find_root(a)<br>rb = find_root(b)"]
    C --> D{"ra == rb ?"}
    D -->|"是"| E["已經同一群<br>不用做事"]
    D -->|"否"| F{"sz[ra] < sz[rb] ?"}
    F -->|"是"| G["swap(ra, rb)"]
    F -->|"否"| H["保持不變"]
    G --> I["parent[rb] = ra<br>sz[ra] += sz[rb]"]
    H --> I
    B -->|"否，查詢"| J["比較 find_root(a)<br>和 find_root(b)"]
    J --> K{"root 相同？"}
    K -->|"是"| L["輸出 YES"]
    K -->|"否"| M["輸出 NO"]

8. 完整 C++ 程式模板：

這份程式假設輸入格式是：

n q
op a b
op a b
...

其中：

op = 1：合併 a 和 b
op = 2：查詢 a 和 b 是否同一群

完整程式：

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> sz;
vector<int> parent;

int find_root(int x) {
    if (parent[x] == x) return x;  // 遞迴終止條件
    return parent[x] = find_root(parent[x]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;  // n = 點的數量, m = 操作數量

    sz.assign(n + 1, 1);
    parent.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    int op, a, b;
    for (int i = 0; i < m; i++) {
        cin >> op >> a >> b;
        int ra = find_root(a);
        int rb = find_root(b);
        if (op == 1) {  // 合併

            if (ra == rb) continue;                     // 兩個已經合併了，所以不用再合併。
            if (sz[ra] < sz[rb]) swap(ra, rb);  // 大的當 a ，讓小的 b 接到大的 a。

            parent[rb] = ra;
            sz[ra] += sz[rb];

        } else {  // 查詢是否同組
            if (ra == rb) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }

    return 0;
}

9. 範例測試

輸入：

過程：

1 1 2：合併 1 和 2
1 2 3：合併 2 和 3，所以 1、2、3 同群
2 1 3：查詢 1 和 3，是同群
2 1 4：查詢 1 和 4，不同群
1 4 5：合併 4 和 5
2 4 5：查詢 4 和 5，是同群

輸出：

YES
NO
YES

例題

P-7-2. 開車蒐集寶物
參加一個蒐集寶物的遊戲，你拿到一個地圖，地圖上有 n 個藏寶點，每個藏寶點有若
干價值的寶物，由於你的團隊是最頂尖的，只要能到達藏寶點一定可以取得該藏寶點
的寶藏。從地圖上看得到一共有 m 條道路，每條道路連接兩個藏寶點，而且每條道路
都是雙向可以通行的。在遊戲的一開始，你可以要求直升機將你的團隊運送到某個藏
寶點，而且你可以獲得一部車與充足的油料，但是直升機的載送只有一次，所以你必
須決定要從哪裡開始才可以獲得最多的寶藏總價值。
Time limit: 1 秒
輸入格式：第一行是兩個正整數 n 與 m，代表藏寶地點數與道路數，地點是以 0~n-1編號，第二行 n 個非負整數，依序是每一個地點的寶藏價值，每個地點的寶藏價值
不超過 100。接下來有 m 行，每一行兩個整數 a 與 b 代表一個道路連接的兩個地點
編號。n 不超過 5e4，m 不超過 5e5。兩點之間可能有多條道路，有些道路的兩端點
可能是同一地點。
輸出：最大可以獲得的寶藏總價值。

範例一輸入：
7 6
5 2 4 2 1 1 8
5 1
1 3
1 4
2 0
2 0
3 3
範例一輸出：
9

解答

#include<bits/stdc++.h>
using namespace std;
#define int long long

vector<int> parent;
vector<int> sz;
vector<int> w;


int find_root(int x){
    if(parent[x] == x) return x;
    return parent[x] = find_root(parent[x]);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n,m;
    cin>>n>>m;          // 點 = 0~n-1, m = 邊數
    
    parent.resize(n);
    sz.resize(n,1);
    w.resize(n);
    
    for(int i=0;i<n;i++){
        parent[i] = i;
        cin>>w[i];
    }
    
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        
        int ra = find_root(a);
        int rb = find_root(b);
        
        if(ra == rb) continue;
        if(sz[ra] < sz[rb]) swap(ra,rb);
        
        parent[rb] = ra;
        sz[ra] += sz[rb];
        w[ra] += w[rb];
        
    }
    
    
    int ma=0;
    for(int i:w){
        ma=max(ma,i);
    }
    
    cout<<ma;
    
    
    return 0;
}

練習題：A - Disjoint Set Union

程式碼

#include <bits/stdc++.h>
using namespace std;

vector<int> parent;
vector<int> sz;

int find_root(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find_root(parent[x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;  // 信件： 1~n ，操作數：m

    parent.assign(n + 1, 0);
    sz.assign(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    int op, a, b;
    while (m--) {
        cin >> op >> a >> b;
        int ra = find_root(a);
        int rb = find_root(b);
        if (op == 0) {
            if (ra == rb) continue;
            if (sz[ra] < sz[rb]) swap(ra, rb);

            parent[rb] = ra;
            sz[ra] += sz[rb];

        } else {
            cout << (ra == rb) << "\n";
        }
    }
    return 0;
}

練習題(較難)：d449. 垃圾信件

程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<int> parent;
vector<int> sz;
vector<int> id;

int find_root(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find_root(parent[x]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;

    while (cin >> n >> m) {
        // 最多每次 op=2 都新增一個節點，所以要開 n + m + 5
        parent.assign(n + m + 5, 0);
        sz.assign(n + m + 5, 0);
        id.assign(n + 1, 0);

        int tot = n;     // 目前用到的 DSU 節點編號
        int ans = n;     // 目前類別數

        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            sz[i] = 1;
            id[i] = i;
        }

        while (m--) {
            int op;
            cin >> op;

            if (op == 1) {
                int a, b;
                cin >> a >> b;

                int ra = find_root(id[a]);
                int rb = find_root(id[b]);

                if (ra == rb) continue;

                if (sz[ra] < sz[rb]) swap(ra, rb);

                parent[rb] = ra;
                sz[ra] += sz[rb];

                ans--;

            } else {
                int a;
                cin >> a;

                int ra = find_root(id[a]);

                // a 本來就自己一類，不用再獨立
                if (sz[ra] == 1) continue;

                // 從原本那一類移出 a
                sz[ra]--;

                // 建立一個新節點代表 a 的新類別
                tot++;
                parent[tot] = tot;
                sz[tot] = 1;
                id[a] = tot;

                ans++;
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

最小生成樹

在一個地圖中有很多條連線，需要將其變成一顆樹(沒有環)而且要路徑最小的演算法，稱為最小生成樹。

P-7-12. 最小生成樹 (*)

輸入一個無向圖 G=(V,E,w)，其中點以 0~n-1 編號，而邊的權重是非負整數。計算
G 的最小生成樹的成本。兩點之間可能有多個邊。
Time limit: 1 秒
輸入格式：第一行是兩個正整數 n 與 m，代表點數與邊數，接下來有 m 行，每行三個
整數 u, v, w 代表一條無向邊(u,v)的長度是 w。n 不超過 1e4，m 不超過 1e5, w
是不超過 1e4 的非負整數。
輸出：輸出最小生成樹的成本，如果不存在則輸出-1。
範例一輸入：
8 10
0 1 6
0 2 4
1 2 5
2 3 9
1 4 1
1 5 1
2 6 2
4 5 3
5 6 8
7 6 1
範例一輸出：
23

以此題為例
如下圖：

alt text

要找出最小生成樹有兩種方法：

法一：併查集(最小生成樹)

將路徑按照權重排序後一一取出，如果連線的兩個點已經在同一集合(ra == rb)，代表會形成環，丟棄(略過)即可。

注意

其實就是在併查集的基礎上把路徑由大到小排序再使用而已

#include <bits/stdc++.h>
using namespace std;

#define tiii tuple<int, int, int>

vector<int> parent;
vector<int> sz;

int find_root(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find_root(parent[x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;  // 點:0~n-1 , 操作:m
    cin >> n >> m;

    priority_queue<
        tiii,
        vector<tiii>,
        greater<tiii> >
        pq;

    parent.assign(n, 0);
    sz.assign(n, 1);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    int x, y, z;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        pq.push({z, x, y});
    }

    int a, b, w, ans = 0,cnt = 0;
    while (!pq.empty()) {
        tie(w, a, b) = pq.top();
        pq.pop();

        int ra = find_root(a);
        int rb = find_root(b);

        if (ra == rb) continue;
        if (sz[ra] < sz[rb]) swap(ra, rb);

        ans += w;
        parent[rb] = ra;
        sz[ra] += sz[rb];
        
        cnt++;
        
        
        // MST 只需要 n - 1 條邊，後面的會被"if (ra == rb) continue;"所以可以直接略過。
        if (cnt == n - 1) break;
    }

    if (cnt == n - 1) {
        cout << ans << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

法二：Prim 演算法

Prim 演算法教學

1. 這題用 Prim 在做什麼

這題 d098 要你找 Minimum Spanning Tree(最小生成樹)：在一張 undirected weighted graph(無向加權圖) 裡，用一些邊把所有點連起來，並讓總邊權最小；如果圖不連通，輸出 -1。題目點編號是 0 ~ n - 1，邊權非負，n <= 1e4、m <= 1e5。(TCIRC Judge 串中電研OJ)

Prim's Algorithm(普里姆演算法) 的核心想法是：

從某一個點開始，慢慢把 MST 長大。
每次都選一條「從已經在 MST 裡的點」連到「還沒進 MST 的點」的最便宜邊。

CP-Algorithms 對 Prim 的描述也是：一開始生成樹只包含任意選的一個點，之後每次加入一條連到未選點的最小權重邊。(競賽程式設計演算法)

2. 生活化理解：Prim 像在鋪電線

想像每個點是村莊，每條邊是兩村之間鋪電線的成本。

一開始我們先選一個村莊，例如 0：

已通電：0
未通電：1, 2, 3, ...

接著每一步都問：

從「已通電的村莊」往外接一個「還沒通電的村莊」，
哪一條線最便宜？

找到最便宜的，就接上去。

接上去以後，已通電村莊變多，可以選的邊也變多。

所以 Prim 不是在找「從 0 到每個點最短路」，而是在找：

每次用最便宜的一條邊，把一個新點納入 MST。

3. Prim 和 Dijkstra 最容易混的地方

你之前有 Dijkstra 程式，所以這裡要特別分清楚。

3.1 Dijkstra 的 `dist[v]`

dist[v] = 從起點 s 走到 v 的最短路徑總長

更新時用：

dist[v] = dist[u] + w;

因為它是「一路從起點累加過來」。

3.2 Prim 的 `dist[v]`

在 Prim 裡我們也常開一個 dist 或 key，但意思不同：

dist[v] = 目前把 v 接進 MST 的最便宜單條邊成本

更新時只用：

dist[v] = w;

不是：

dist[v] = dist[u] + w;

因為 MST 不管「從起點走到 v 的路徑總長」，它只在意「把 v 接進目前這棵樹的那條邊多少錢」。

USACO Guide 對 Prim 的 priority queue 寫法也說，從 priority queue 取出最接近 MST 的點，然後把它的鄰居加入 priority queue；起點可任選。([USACO 指南][3])

4. Prim 的核心不變量

Prim 每一步都維持這個狀態：

vis[v] = true 代表 v 已經被加入 MST
vis[v] = false 代表 v 還沒加入 MST

priority queue 裡面放的是：

{接進 MST 的邊權, 點}

也就是：

{w, v}

不是 Dijkstra 的：

{從起點到 v 的距離, v}

5. 流程圖

flowchart TD
    A["讀入 n, m"] --> B["建立無向圖 adjacency list<br>g[u].push_back({v,w})<br>g[v].push_back({u,w})"]
    B --> C["選起點 0<br>pq.push({0, 0})"]
    C --> D["pq 取出目前最小成本 {d, u}"]
    D --> E{"u 已經在 MST 嗎？"}
    E -->|"是"| D
    E -->|"否"| F["把 u 加入 MST<br>vis[u] = true<br>ans += d<br>cnt++"]
    F --> G["檢查 u 的所有鄰居 v"]
    G --> H{"v 還沒進 MST？"}
    H -->|"是"| I["pq.push({w, v})"]
    H -->|"否"| J["跳過"]
    I --> K{"pq 還有邊嗎？"}
    J --> K
    K -->|"有"| D
    K -->|"沒有"| L{"cnt == n ?"}
    L -->|"是"| M["輸出 ans"]
    L -->|"否"| N["圖不連通<br>輸出 -1"]

6. 為什麼可以從 0 開始

這題點編號是：

0 ~ n - 1

Prim 的起點可以任選，所以我們直接選：

pq.push({0, 0});

意思是：

把點 0 當作第一個進 MST 的點，成本是 0。

注意這個 0 成本不是一條真的邊，只是讓演算法從點 0 開始。

7. 用範例小圖走一次

假設圖長這樣：

0 -- 1，權重 1
0 -- 2，權重 2
1 -- 2，權重 1

從 0 開始。

一開始：

MST 裡：0
pq 裡：{0,0}
ans = 0

取出 {0,0}，把 0 加入 MST。

把 0 的邊丟進 pq：

{1,1}
{2,2}

接著取最小 {1,1}，把 1 加入 MST：

ans = 1
MST 裡：0, 1

把 1 的邊丟進 pq，其中 1-2 權重 1：

{1,2}
{2,2}

取最小 {1,2}，把 2 加入 MST：

ans = 2
MST 裡：0, 1, 2

全部點都進 MST，答案是：

MST 選到的是：

0-1，權重 1
1-2，權重 1

不是 0-2 權重 2。

8. 這題的 Prim 寫法，不用 struct

這份寫法最適合你現在理解，因為 priority queue 裡只存：

{邊權, 點}

完整程式：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> g(n);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        // 題目是無向圖，所以兩邊都要加
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    priority_queue<
        pair<int, int>,
        vector<pair<int, int>>,
        greater<pair<int, int>>
    > pq;

    vector<int> vis(n, 0);

    long long ans = 0;
    int cnt = 0;

    // Prim 起點可以任選；這題點是 0 ~ n - 1，所以從 0 開始
    pq.push({0, 0});  // {接進 MST 的成本, 點}

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();

        int d = cur.first;
        int u = cur.second;

        // 如果 u 已經進 MST，這筆資料是舊的，跳過
        if (vis[u]) continue;

        // 把 u 加入 MST
        vis[u] = 1;
        ans += d;
        cnt++;

        // 把 u 連出去、能接到新點的邊放進 pq
        for (auto e : g[u]) {
            int v = e.first;
            int w = e.second;

            if (!vis[v]) {
                pq.push({w, v});
            }
        }
    }

    if (cnt == n) {
        cout << ans << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

9. 程式逐段解釋

9.1 建圖

vector<vector<pair<int, int>>> g(n);

意思是：

g[u] 存所有從 u 連出去的邊
pair<int,int> = {v, w}

例如：

g[u].push_back({v, w});

代表：

u 可以連到 v，成本 w

因為這題是無向圖，所以一定要寫兩次：

g[u].push_back({v, w});
g[v].push_back({u, w});

9.2 priority queue 裡放什麼

priority_queue<
    pair<int, int>,
    vector<pair<int, int>>,
    greater<pair<int, int>>
> pq;

這是 min-heap(小根堆)。

裡面每筆資料是：

{d, u}

意思是：

目前有一條成本 d 的邊，可以把 u 接進 MST

9.3 為什麼 `pq.push({0, 0})`

pq.push({0, 0});

意思是：

從點 0 開始。
把 0 加進 MST 的成本先當作 0。

這不是說有一條權重 0 的邊，而是演算法啟動用的假成本。

9.4 為什麼要 `vis`

if (vis[u]) continue;

因為同一個點可能被很多條邊推進 priority queue。

例如：

0 -- 2，權重 10
1 -- 2，權重 3

點 2 可能先被 {10, 2} 推進 pq，後來又被 {3, 2} 推進 pq。

如果 {3, 2} 先被拿出來，2 已經進 MST 了，之後 {10, 2} 再被拿出來時，就要跳過。

10. 為什麼這版不用 `dist`

Prim 有兩種常見寫法：

10.1 懶惰版 Lazy Prim

也就是我上面給你的版本。

它的做法是：

看到一條可以連到未拜訪點的邊，就丟進 pq。
之後如果拿出來時那個點已經進 MST，就跳過。

優點：

比較好懂，程式短。

缺點：

pq 裡會有一些舊資料。

但這題 m <= 1e5，完全可以接受。(TCIRC Judge 串中電研OJ)

10.2 類 Dijkstra 版 Prim

也可以寫 dist[v]：

dist[v] = 把 v 接進 MST 的目前最小邊權

更新時：

if (!vis[v] && w < dist[v]) {
    dist[v] = w;
    pq.push({dist[v], v});
}

這比較像你之前的 Dijkstra，但初學我建議先看 Lazy Prim，因為更直接：

把所有候選邊丟進 pq，每次拿最小的。

11. Lazy Prim 的核心記法

你可以把它背成 4 句：

1. 從任一點開始，先 push {0, 起點}
2. 每次從 pq 拿出最便宜的候選邊
3. 如果這個點還沒進 MST，就收下它，ans += 邊權
4. 把這個點連到未拜訪點的邊都丟進 pq

12. 跟 Kruskal 的差別

演算法	怎麼選邊	需要 DSU 嗎	起點
Kruskal	全部邊排序，從小到大選不成環的邊	需要	沒有
Prim	從目前 MST 往外長，每次選最便宜的外接邊	不需要	可以任選

這題兩種都可以。你剛學 DSU，所以 Kruskal 很直覺；但如果你想練 priority queue，Prim 也很適合。

13. 你最容易寫錯的地方

13.1 忘記無向圖要加兩邊

錯誤：

g[u].push_back({v, w});

正確：

g[u].push_back({v, w});
g[v].push_back({u, w});

13.2 把 Prim 寫成 Dijkstra

錯誤：

pq.push({d + w, v});

這是 Dijkstra 味道。

Prim 要放單條邊權：

pq.push({w, v});

因為 Prim 每次在比的是：

哪條邊最便宜可以接新點

不是：

從起點到 v 的總距離是多少

13.3 最後檢查條件寫錯

Kruskal 檢查：

cnt == n - 1

因為 Kruskal 的 cnt 通常是「選了幾條邊」。

Prim 這份程式裡檢查：

cnt == n

因為這裡的 cnt 是「有幾個點進入 MST」。

兩個不要搞混。

使用這方法找出所有最短路徑，最後加在一起。

注意

比較需要注意的是對於相同的點不要 push 之後就 vis = 1，應該要全部都加到 pq 中，然後拿出來 vis == 1 跳過、vis =1。

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

int main() {
    int n, m;
    cin >> n >> m;  // 點:0~n, 操作:m

    vector<int> vis(n);
    vector<vector<pii>> vec(n);

    int x, y, w, u, d, v;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> w;
        vec[x].push_back({y, w});
        vec[y].push_back({x, w});  // 雙向
    }

    priority_queue<
        pii,
        vector<pii>,
        greater<pii>>
        pq;

    pq.push({0, 0});  // 隨便找一個起點

    int ans = 0, cnt = 0;
    while (!pq.empty()) {
        tie(d, u) = pq.top();
        pq.pop();

        // 如果 u 已經進 MST，這筆資料是舊的，跳過
        if (vis[u]) continue;
        vis[u] = 1;
        ans += d;
        cnt++;

        for (pii pp : vec[u]) {
            tie(v, w) = pp;

            if (!vis[v]) {
                pq.push({w, v});
            }
        }
    }

    if (cnt == n) {
        cout << ans;
    } else {
        cout << -1;
    }

    return 0;
}

圖論

BFS

實作

P-7-1. 探索距離

DFS

P-7-2. 開車蒐集寶物

DAG 與 topological sort

習題

UVA-10305

f167. m4a1-社團 Club

a552. 模型

m933. 3. 邏輯電路

基礎習題

d092: P-7-3. 機器人走棋盤 (APCS 201906)

d093: P-7-4. 方格棋盤的最少轉彎數路線

d094: Q-7-5. 闖關路線 (APCS201910)

Q-7-7. AOV 最早完工時間

有權重的邊

D - Transit Tree Path

D - Even Relation

Dijkstra 演算法用來計算一個圖中一點到其他點的最短路徑

1. 為什麼 pop 出來就能確定

2. 核心概念：dist[v] 不是答案，一開始只是「目前找到的最好答案」

3. 為什麼「最小的點」可以直接確定？

4. Relaxation(鬆弛) 是什麼？

5. 流程圖

6. 用一個小圖走一次

7. 實際執行表

8. C++ 標準模板

9. 你可以這樣記 Dijkstra

10. 最常見錯誤

10.1 把點 push 進 Priority Queue 時就當成確定

10.2 有負邊還用 Dijkstra

10.3 priority_queue 預設是 Max-Heap

11. 最後用一句直覺收斂

例題

練習題

D - Super Takahashi Bros.

Single Source Shortest Path

併查集

1. 併查集在解決什麼問題

2. 核心原理

3. find_root 是什麼

4. path compression(路徑壓縮)

5. 合併兩個集合

6. union by size(依大小合併)

7. 視覺化流程

8. 完整 C++ 程式模板：

9. 範例測試

例題

練習題：A - Disjoint Set Union

練習題(較難)：d449. 垃圾信件

最小生成樹

P-7-12. 最小生成樹 (*)

法一：併查集(最小生成樹)

法二：Prim 演算法

1. 這題用 Prim 在做什麼

2. 生活化理解：Prim 像在鋪電線

3. Prim 和 Dijkstra 最容易混的地方

3.1 Dijkstra 的 dist[v]

3.2 Prim 的 dist[v]

4. Prim 的核心不變量

5. 流程圖

6. 為什麼可以從 0 開始

7. 用範例小圖走一次

8. 這題的 Prim 寫法，不用 struct

9. 程式逐段解釋

9.1 建圖

9.2 priority queue 裡放什麼

9.3 為什麼 pq.push({0, 0})

9.4 為什麼要 vis

10. 為什麼這版不用 dist

10.1 懶惰版 Lazy Prim

10.2 類 Dijkstra 版 Prim

11. Lazy Prim 的核心記法

12. 跟 Kruskal 的差別

13. 你最容易寫錯的地方

13.1 忘記無向圖要加兩邊

13.2 把 Prim 寫成 Dijkstra

13.3 最後檢查條件寫錯

2. 核心概念：`dist[v]` 不是答案，一開始只是「目前找到的最好答案」

10.3 `priority_queue` 預設是 Max-Heap

3.1 Dijkstra 的 `dist[v]`

3.2 Prim 的 `dist[v]`

9.3 為什麼 `pq.push({0, 0})`

9.4 為什麼要 `vis`

10. 為什麼這版不用 `dist`