題目傳送門：

P5994 [PA 2014] Kuglarz - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)

前言：

? ? ? ? 本題涉及到最小生成樹中的 kruskal? 算法和并查集算法，圖論基礎概念兩大知識點，瞎按對萊索沒有學過圖論的或最小生成樹的可能會對這道題無從下手，學過最小生成樹和圖論的初學者對這道題可以說是非常好的歷練。難度可以給到中等偏上（很簡單的呀）。

#題目核心目標：

? ? ? ? 這道題的很新目標是確定最少花費，從而保證能猜出哪些被子底下藏著球，而解題的關鍵在于將問題轉化成最小生成樹問題。本題將詳細境界。

##問題分析轉化：

? ? ? ? 1、信息關聯與節點表示：

? ? ? ? ? ? ? ? 把每個被子看做圖中的一個節點。對于一個被子序列，我們要確定每個被子是否藏球，而通過魔術師提供的關于區間??內藏球總數奇偶性的信息，就可以逐步推斷出每個被子的情況。

? ? ? ? ? ? ? ? 例如，知道區間??的詢問都對應途中的一條邊，變得兩個端點分別是和?,變得權值就是這次詢問的花費??。因為我們可以利用這個區間的奇偶性信息來連接這兩個端點所代表的節點狀態。

3、問題等價性：

? ? ? ? ? ? ? ? 我們的目標使用最少的花費來獲取足夠的信息來確定所有杯子里是否藏球，這就相當于在圖中找到一個變得集合，使得這些邊能夠連接所有節點，并且這些邊的權值總和最小，恰好就是我們經典的最小生成樹問題。

###最小生成樹選擇-Kruskal 算法：

? ? ? ? 1、具體步驟：

? ? ? ? ? ? ? ? 1.1、邊的排序：將所有表示詢問的邊按照花費從小到大進行排序。這里做的目的是優先選擇花費曉得詢問，以滿足最小花費的要求。

? ? ? ? ? ? ? ? 1.2、并查集的使用：

• 并查集是一種用于處理不相交集合合并與查詢問題的數據結構。在本題中，我們使用并查集來判斷加入一條邊后是否會形成環。
• 初始時，每個節點的父節點就是它自身，表示每個節點都屬于一個獨立的集合。
• 對于每條邊，我們查找其兩個端點所在集合的根節點。如果兩個端點的根節點不同，說明這兩個端點屬于不同的集合，加入這條邊不會形成環，我們就將這條邊加入到最小生成樹中，并合并這兩個集合（即將一個集合的根節點指向另一個集合的根節點）。
• 如果兩個端點的根節點相同，說明這兩個端點已經在同一個集合中，加入這條邊會形成環，我們就跳過這條邊。

####代碼：

#include <bits/stdc++.h>
using namespace std;
const int M = 2005;
struct E {int u, v, w;E(int u, int v, int w) : u(u), v(v), w(w) {}bool operator<(const E& t) const {return w < t.w;}
};
int p[M];
int find(int x) {if (p[x] != x) {p[x] = find(p[x]);}return p[x];
}
void un(int x, int y) {int rx = find(x);int ry = find(y);if (rx != ry) {p[rx] = ry;}
}int main() {int n;cin >> n;vector<E> e;for (int i = 1; i <= n; ++i) {for (int j = i; j <= n; ++j) {int o;cin >> o;e.emplace_back(i - 1, j, o);}}for (int i = 0; i <= n; ++i) {p[i] = i;}sort(e.begin(), e.end());long long C = 0;for (const auto& g : e) {int u = g.u;int v = g.v;int w = g.w;int ru = find(u); int ry = find(v);if (ru != ry) {un(u, v);C += w;}}cout << C << endl;return 0;
}