#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定義活動結(jié)構(gòu)體
struct Activity {
    int start;  // 開始時間
    int end;    // 結(jié)束時間
};

// 排序規(guī)則：按結(jié)束時間升序
bool compare(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

// 選擇最多不沖突活動
vector<Activity> selectMaxActivities(vector<Activity>& activities) {
    vector<Activity> result;
    if (activities.empty()) return result;

    // 1. 按結(jié)束時間排序
    sort(activities.begin(), activities.end(), compare);

    // 2. 選擇第一個活動（最早結(jié)束）
    result.push_back(activities[0]);
    int lastEnd = activities[0].end;

    // 3. 遍歷后續(xù)活動，選擇不沖突的（開始時間>=上一個結(jié)束時間）
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= lastEnd) {
            result.push_back(activities[i]);
            lastEnd = activities[i].end;  // 更新最后一個活動的結(jié)束時間
        }
    }
    return result;
}

int main() {
    vector<Activity> activities = {
        {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}
    };

    vector<Activity> selected = selectMaxActivities(activities);

    // 輸出結(jié)果
    cout << "選擇的活動（開始時間, 結(jié)束時間）：" << endl;
    for (auto& act : selected) {
        cout << "(" << act.start << ", " << act.end << ")" << endl;
    }
    cout << "最多可選擇 " << selected.size() << " 個活動" << endl;
    return 0;
}

選擇的活動（開始時間, 結(jié)束時間）：
(1, 4)
(5, 7)
(8, 11)
(12, 16)
最多可選擇 4 個活動

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 計算哈夫曼編碼的總長度
int huffmanCodeTotalLength(const vector<int>& frequencies) {
    // 最小堆：priority_queue<Type, Container, Compare>
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 1. 將所有頻率入堆
    for (int freq : frequencies) {
        minHeap.push(freq);
    }

    int totalLength = 0;  // 總編碼長度

    // 2. 合并節(jié)點，直到堆中只剩1個節(jié)點
    while (minHeap.size() > 1) {
        // 取出兩個最小頻率
        int first = minHeap.top();
        minHeap.pop();
        int second = minHeap.top();
        minHeap.pop();

        // 合并后的新節(jié)點頻率
        int merged = first + second;
        totalLength += merged;  // 合并節(jié)點的頻率即編碼長度貢獻

        // 新節(jié)點入堆
        minHeap.push(merged);
    }

    return totalLength;
}

int main() {
    // 字符頻率：a:5, b:9, c:12, d:13, e:16, f:45
    vector<int> frequencies = {5, 9, 12, 13, 16, 45};

    int total = huffmanCodeTotalLength(frequencies);
    cout << "哈夫曼編碼的總長度：" << total << endl;  // 輸出：224
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <stdexcept>  // 用于邊界校驗異常
using namespace std;

const int INF = INT_MAX;

vector<int> dijkstra(int n, int source, const vector<vector<pair<int, int>>>& adj) {
    // 邊界校驗：源點合法性
    if (source < 0 || source >= n) {
        throw invalid_argument("源點超出節(jié)點范圍！");
    }

    vector<int> dist(n, INF);
    dist[source] = 0;

    // 最小堆：(當前距離, 節(jié)點)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    minHeap.push({0, source});

    while (!minHeap.empty()) {
        auto [currentDist, u] = minHeap.top();  // C++17結(jié)構(gòu)化綁定
        minHeap.pop();

         if (currentDist > dist[u]) continue;

        // 遍歷u的所有鄰接節(jié)點
        for (auto [v, w] : adj[u]) {
            // 松弛操作：更新dist[v]
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                minHeap.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main() {
    int n = 6;  // 節(jié)點數(shù)（0~5）
    vector<vector<pair<int, int>>> adj(n);  // 局部鄰接表，替代全局變量

    // 構(gòu)建圖（邊：u->v，權(quán)w）
    adj[0].emplace_back(1, 2);  // emplace_back比push_back更高效（直接構(gòu)造對象）
    adj[0].emplace_back(2, 4);
    adj[1].emplace_back(2, 1);
    adj[1].emplace_back(3, 7);
    adj[2].emplace_back(4, 3);
    adj[3].emplace_back(5, 1);
    adj[4].emplace_back(3, 2);
    adj[4].emplace_back(5, 5);

    int source = 0;
    try {
        vector<int> dist = dijkstra(n, source, adj);

        // 輸出正確結(jié)果
        cout << "源點 " << source << " 到各節(jié)點的最短距離：" << endl;
        for (int i = 0; i < n; ++i) {
            if (dist[i] == INF) {
                cout << "到節(jié)點 " << i << "：不可達" << endl;
            } else {
                cout << "到節(jié)點 " << i << "：" << dist[i] << endl;
            }
        }
    } catch (const invalid_argument& e) {
        // 捕獲邊界校驗異常
        cerr << "錯誤：" << e.what() << endl;
        return 1;
    }

    return 0;
}

源點 0 到各節(jié)點的最短距離：
到節(jié)點 0：0
到節(jié)點 1：2
到節(jié)點 2：3（0→1→2）
到節(jié)點 3：8（0→1→2→4→3）
到節(jié)點 4：6（0→1→2→4）
到節(jié)點 5：9（0→1→2→4→3→5）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定義邊結(jié)構(gòu)體
struct Edge {
    int u;      // 起點
    int v;      // 終點
    int weight; // 邊權(quán)
};

// 并查集（Union-Find）：維護連通分量
class UnionFind {
private:
    vector<int> parent;  // 父節(jié)點
    vector<int> rank;    // 秩（用于路徑壓縮優(yōu)化）
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 初始父節(jié)點為自身
        }
    }

    // 查找根節(jié)點（路徑壓縮）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 遞歸壓縮路徑
        }
        return parent[x];
    }

    // 合并兩個連通分量（按秩合并）
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return false;  // 已在同一分量

        // 秩小的樹合并到秩大的樹
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
        return true;
    }
};

// Kruskal算法：返回MST的總邊權(quán)
int kruskal(int n, vector<Edge>& edges) {
    // 1. 按邊權(quán)升序排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    UnionFind uf(n);
    int mstTotal = 0;  // MST總邊權(quán)
    int edgeCount = 0; // 已選邊數(shù)

    // 2. 遍歷邊，選擇不構(gòu)成環(huán)的邊
    for (auto& edge : edges) {
        if (uf.unite(edge.u, edge.v)) {
            mstTotal += edge.weight;
            edgeCount++;

            // MST需n-1條邊，提前退出
            if (edgeCount == n - 1) break;
        }
    }

    // 若邊數(shù)不足n-1，說明圖不連通
    return (edgeCount == n - 1) ? mstTotal : -1;
}

int main() {
    int n = 5;  // 節(jié)點數(shù)（0~4）
    vector<Edge> edges = {
        {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5},
        {2, 4, 7}, {3, 4, 9}
    };

    int mstTotal = kruskal(n, edges);
    if (mstTotal == -1) {
        cout << "圖不連通，無法構(gòu)建MST" << endl;
    } else {
        cout << "最小生成樹的總邊權(quán)：" << mstTotal << endl;  // 輸出：16
    }
    return 0;
}