首頁

# 前言

這篇文章只是概念講解，沒有視覺化輸出，專注在解決問題的方法，與測資示範如何生成。

以下我統一都挑選 CSES 與 leetcode 的題目，有些是我手寫的程式碼有些是 AI 寫的， leetcode 的題目就不放程式碼了上面很多題解，如果看不懂貼上去叫 AI 每行註解應該就看得懂了。

以下的題目不一定都完美對應到老師的題目，不過核心概念會是對應到的。

# 外送與物流最佳配送路線（Graph + Shortest Path）

根據題目這題有三個子問題， 一般圖 、 負權重圖 、 動態變化圖 ，分別對應到三個題目。
以下三題都來自 CSES

# Shortest Routes I

題目網址: https://cses.fi/problemset/task/1671

# 講解

這題就是就是經典的用 Dijkstra's Algorithm 來解決問題，我的寫法可能跟一般網路上教學的模板有些差異，不過都差不多

Dijkstra's Algorithm 的核心就是每次都挑選最短的路徑來走，而可以快速求出最大值或最小值的資料結構就是 heap

這邊要注意丟進去 priority_queue 權重是負的，用來完成最短路徑挑選，記得拿出來的時候要轉回去

# AC 程式碼

#include <bits/stdc++.h>
using namespace std;
#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);
typedef long long LL;
#define N 100005
int n,m;
priority_queue<pair<LL,int>> pq;
LL dis[N];
vector<pair<int,int>> adj[N];
int main(){
    Rabbir_Reaper
    cin>>n>>m;
    for(int i=0,a,b,c;i<m;i++){
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
    }
    fill(dis,dis+n+1,LLONG_MAX);
    dis[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        pair<int,int> temp = pq.top();pq.pop();
        if(-temp.first > dis[temp.second]) continue;
        for(auto &u:adj[temp.second]){
            if(dis[u.first] > dis[temp.second]+u.second){
                dis[u.first] = dis[temp.second]+u.second;
                pq.push({-dis[u.first],u.first});
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
}

# Cycle Finding

題目網址: https://cses.fi/problemset/task/1197

# 講解

這題就是 Bellman-Ford Algorithm 的裸題， Bellman-Ford Algorithm 的要點就在， n 個點要連通至少需要 n-1 條邊，所以找到最短路徑迴圈執行 n-1 次即可，到了第 n 次正常的圖最短路徑不會有任何變化，如果有負環的話，就會出現更小的路徑，確定有負環後要返回 n 個點確保在負環內，因為負環可能跟整個圖相比很小，在執行 n-1 次時負環已經繞了很多圈然後路徑影響到了外面的 node ，這邊就是主要的邏輯了，剩下的部分就根據題目輸出而已。

# AC 程式碼

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);
const int N = 2505;
int n, m;
int parent[N];
LL dis[N];
int main(){
    Rabbir_Reaper
    cin >> n >> m;
    vector<vector<int>> edges;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({a, b, c});
    }
    fill(dis, dis + n + 1, 0);
    int cycle_end = -1; // 記錄參與負環的節點
    for(int iter=0,u,v,w; iter < n; iter++){
        cycle_end = -1;
        for(auto &temp : edges){
            u = temp[0];
            v = temp[1];
            w = temp[2];
            if(dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                parent[v] = u;
                if(iter == n - 1){
                    cycle_end = v;
                }
            }
        }
    }
    if(cycle_end == -1){
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for(int i = 0; i < n; i++){
        cycle_end = parent[cycle_end];
    }
    vector<int> cycle;
    int curr = cycle_end;
    do {
        cycle.push_back(curr);
        curr = parent[curr];
    } while(curr != cycle_end);
    reverse(cycle.begin(), cycle.end());
    for(int i = 0; i < (int)cycle.size(); i++){
       cout << cycle[i] << " ";
    }
    cout << cycle[0];
}
# Flight Discount


題目網址: https://cses.fi/problemset/task/1195


# 講解


這題雖然跟老師的題目有三個線段要變更不太一樣，不過實際上寫法差不多， dp  定義是一樣的，增加多個狀態的判斷即可，算是同類型的問題。


# AC 程式碼


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // 鄰接表：adj [u] 存放從 u 出發的邊 (v, w)
    vector<vector<pair<int, ll>>> adj(n + 1);
    
    for (int i = 0; i < m; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
    }
    
    //dp [used][v] = 到達城市 v，已使用 used 張折扣券的最小花費
    //used = 0: 還沒用過折扣券
    //used = 1: 已經用過折扣券
    vector<vector<ll>> dp(2, vector<ll>(n + 1, INF));
    
    // 優先佇列：(目前花費，折扣券使用狀態，目前城市)
    // 使用 greater<> 實現最小堆
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    
    // 起點初始化：在城市 1，折扣券還沒用，花費為 0
    dp[0][1] = 0;
    pq.push({0, 0, 1});
    
    while (!pq.empty()) {
        auto [d, used, u] = pq.top();
        pq.pop();
        
        // 剪枝：如果這個狀態已經有更好的解，跳過
        if (d > dp[used][u]) continue;
        
        // 遍歷從 u 出發的所有邊
        for (auto [v, w] : adj[u]) {
            
            // 轉移 1：不使用折扣券（無論折扣券是否已用過）
            ll new_cost = dp[used][u] + w;
            if (new_cost < dp[used][v]) {
                dp[used][v] = new_cost;
                pq.push({new_cost, used, v});
            }
            
            // 轉移 2：使用折扣券（前提是還沒用過）
            if (used == 0) {
                ll discounted_cost = dp[0][u] + w / 2;
                if (discounted_cost < dp[1][v]) {
                    dp[1][v] = discounted_cost;
                    pq.push({discounted_cost, 1, v});
                }
            }
        }
    }
    
    // 答案：到達城市 n 的最小花費
    // 可能用了折扣券，也可能沒用（如果不用更划算的話）
    ll ans = min(dp[0][n], dp[1][n]);
    cout << ans << "\n";
    
    return 0;
}
# 社交媒體朋友推薦系統（Graph + BFS/DFS/Union-Find）


這題我認為第三題的細節沒有說清楚，很難去判斷完整的實作，不過第一二題還是比較明確的。


第一題根據




朋友推薦 (共同朋友)： 使用 BFS/DFS 查找距離為 2 的節點，並計算共同朋友數量進行排序

如果是要找最多距離為 2 相連的節點，那換句話說就是找圖的中心，不然其實對每個點 dfs or bfs  窮舉也行。

這邊提供一題 BFS  的裸題，可能會感覺與原題差很多，不過實作其實差不多，把相距的距離也一起丟進 queue  就好了，窮舉每個點就能知道誰最多。




第二題根據




社群偵測： 使用 Union-Find 演算法，將所有用戶劃分為互不相交的社群

這邊其實有講跟沒講一樣，也沒有說要求什麼，不過應該就是練習並查集的實作。




第三題




關係強度： 透過計算共同興趣或標籤的權重，優化邊權重，並利用 DFS 進行加權搜尋。

推薦測試： 測試節點 XX (朋友少) 和節點 YY (朋友多) 的推薦列表。

這邊提到的推薦列表，標籤的權重，如果是計算點與點之間聯繫的權重，如果按找權重大小排序，那就只是最短路徑反過來求而已，不太清楚題意，所以這邊就沒放題目了。




# Message Route


# AC 程式碼


#include <bits/stdc++.h>
using namespace std;
#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);
#define N 100005
int n,m;
vector<int> adj[N],p(N,0);
bool visit[N];
int main(){
    Rabbir_Reaper
    cin>>n>>m;
    for(int i=0,u,v;i<m;i++){
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    queue<int> que;
    visit[1]=true;
    p[1]=0;
    que.push(1);
    while(!que.empty()){
        int x=que.front();que.pop();
        bool c=0;
        for(auto &u:adj[x]){
            if(visit[u]) continue;
            visit[u]=1;
            p[u]=x;
            if(u == n){
                c=1;
                break;
            }
            que.push(u);
        }
        if(c) break;
    }
    if(p[n]==0) cout<<"IMPOSSIBLE";
    else{
        vector<int> ans;
        ans.push_back(n);
        n=p[n];
        while(n != 0){
            ans.push_back(n);
            n=p[n];
        }
        cout<<ans.size()<<"\n";
        for(int i=(int)ans.size()-1;i>=0;i--) cout<<ans[i]<<" ";
    }
}
# Road Construction


題目網址: https://cses.fi/problemset/task/1676


# AC 程式碼


#include <bits/stdc++.h>
using namespace std;
#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);
const int N = 100005;
int find(int x,vector<int> &boss){
    if(boss[x] < 0) return x;
    else return boss[x] = find(boss[x],boss);
}
int main(){
    Rabbir_Reaper
    int n,m,mx=1;
    cin>>n>>m;
    vector<int> boss(n+1,-1);
    for(int i=0,a,b;i<m;i++){
        cin>>a>>b;
        a = find(a,boss);
        b = find(b,boss);
        if(a != b){
            if(boss[a] < boss[b]) swap(a,b);
            boss[a] += boss[b];
            boss[b] = a;
            mx = max(mx,-boss[a]);
            n--;
        }
        cout<<n<<" "<<mx<<"\n";
    }
}
# 從缺


# 股票交易最佳化排程（Dynamic Programming + Stack/Queue）


這題 leetcode  有完美對應到的一系列題目，除了第一題，這裡的二、三題我認為是蠻難的，我第一次寫第二題的時候不看答案大概想了三天三夜。


這邊 leetcode  有詳細的教學，我這邊就不做任何解釋了。


# 121. Best Time to Buy and Sell Stock


題目網址: https://leetcode.com/problems/best-time-to-buy-and-sell-stock


# 122. Best Time to Buy and Sell Stock II


題目網址: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii


# 714. Best Time to Buy and Sell Stock with Transaction Fee


題目網址: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee


# 地圖路網與洪水氾濫模擬（Matrix/Grid + Backtracking）


老師的題目真的是不知道在寫什麼，不過整來說應該就是判斷連通區域，連通區域有多大有幾個，然後矩陣有不同的高度，這邊根據簡單到困難列了三題，最後一題 leetcode  跟老師的題目感覺蠻符合的，不過那題挺難的，那題還有個一維的版本題目叫 水槽(108高中全國賽)  那題就已經很難了，是 窮舉減枝 的題目或者說 回朔法 有興趣可以去看 AP325 Q-2-14. 。


# Counting Rooms


題目網址: https://cses.fi/problemset/task/1192


# 講解


這題基本上就基本的 dfs 。


# AC 程式碼


#include <bits/stdc++.h>
using namespace std;
#define Rabbir_Reaper ios::sync_with_stdio(0);cin.tie(0);
#define N 1005
bool g[N][N];
int n,m,ans=0;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
void dfs(int x,int y){
    if(x<0 || y<0 || x>=n || y>=m || g[x][y]) return;
    g[x][y]=1;
    for(int i=0;i<4;i++){
        dfs(x+dir[i][0],y+dir[i][1]);
    }
}
 
 
int main(){
    Rabbir_Reaper
    cin>>n>>m;
    for(int i=0;i<n;i++){
        char c;
        for(int j=0;j<m;j++){
            cin>>c;
            if(c == '#') g[i][j]=1;
            else g[i][j]=0;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!g[i][j]){
                dfs(i,j);
                ans++;
            }
        }
    }
 
    cout<<ans;
}
# trapping-rain-water


題目網址: https://leetcode.com/problems/trapping-rain-water


這邊放一維的版本，算是為第三題鋪陳，因為根據老師的題目，這邊想不到其他更適合的了。


# LeetCode 407. Trapping Rain Water II


題目網址: https://leetcode.com/problems/trapping-rain-water-ii