CSDN同步
本人并沒有找到本題連結，抱歉。（純屬個人練習題，非本人原創）是以把題目内容 暫時 存放于 洛谷私人題庫 中。
原題連結
簡要題意：
找到一個最小的邊集(E)，使得對任意一個 不等于全集 的點集 (S)，恰好隻有一個頂點在 (S) 裡的邊中 權值最小的那一條 在邊集 (E) 中。
很顯然，我們需要對 (a_i
ightarrow b_i) 連一條權值為 (T_i) 的邊，建圖。
算法一
對于 (30 \%) 的資料，(N leq 10,M leq 20).
首先我們分析一下可以得到：答案肯定是 (N-1) 條邊，即構成一棵 生成樹 。（否則有點沒有被包含，而 整個圖是連通圖，顯然不滿足）
是以，我們隻需要枚舉這 (9) 條邊的選擇方法，然後暴力掃一遍驗證即可。
時間複雜度：(O(C_M^{N-1} imes n)).
實際得分：(30pts).
粗略的計算一下：(C_M^{N-1} imes n = frac{20!}{11! imes 9!} imes 10)，大概是 (1.6 imes 10^5 imes 10 = 1.6 imes 10^6)，可以通過。
算法二
對于 (70 \%) 的資料，(N leq 100)，(M leq 10^3).
對于 (100 \%) 的資料，(N leq 10^4)，(M leq 10^5).
由于算法一的分析，我們得到 選擇的邊構成一棵生成樹 。
下面給出一種貪心。
算法 2.1
既然題目說 “權值最小的那一條在邊集 (E) 中”，那麼枚舉每個點權值最小的那條邊将其删去，如果重複則不删，删到 (n-1) 條邊為止。
時間複雜度：(O(n+m)).
期望得分：(100pts).
實際得分：(0pt).
為什麼會這樣呢？肯定是我們的貪心出錯了。
給出一組反例（其實類似于樣例，把 (2) 和 (3) 換了一下）：
4 4
1 3 2
4 2 4
2 3 3
1 2 1
按照這樣的貪心方法，你的步驟是：
-
枚舉 (1)，并删去 (1
ightarrow 2) 這條邊。
-
枚舉 (2)，因為 (1
ightarrow 2) 已經被删去，是以删去 (2
ightarrow 3) 這條邊。
-
枚舉 (3)，隻有 (3
ightarrow 1) 可以删，是以删去。
發現删去了 (4-1 = 3) 條邊，結束。
你發現哪裡錯了麼？如果你把 (1
ightarrow 2,2
ightarrow 3 ,3
ightarrow 1) 删去，那麼 (4) 的 權值最小的那一條在邊集 (E)中 是不滿足的！
那你說，好啊，那我把最後一條 (3
ightarrow 1) 判斷一下，發現 (3) 已經被連，是以枚舉 (4)，删去 (4
ightarrow 2) 這條邊。
還是錯的！因為對于 (3) 這個點，它最小的邊權是 (3
ightarrow 1)，又沒有被删除！
是以 整個貪心被 ( ext{hack}) 掉，我們需要更嚴謹的貪心。
算法 2.2
對于 (70 \%) 的資料，(N leq 100)，(M leq 10^3).
既然我們不能一個個枚舉，就去注意另一個性質。
由算法 (1) 的分析可以知道，邊集 (E) 應當是原圖的一棵生成樹。
那麼，一個思路就來了：求最小生成樹。
為什麼最小生成樹是正确的？我們來回憶一下，( exttt{kruskal}) 求 最小生成樹 的過程。
- 用并查集維護每個點所屬連通塊，将取出邊權最小的一條邊，将兩個端點合并。
- 在剩下的邊中選擇一條 兩端點屬于不同連通塊 且 有一端點已被選過 的 邊權最小 的邊，然後合并，取邊。
- 反複做 (2) 步驟 (n-1) 次即可得到 最小生成樹。
那麼顯然的性質：每個點的它邊權最小的那條邊包含于最小生成樹中。如果不然，則應當用邊權最小的邊替換之，非最小生成樹，得證。
是以，求最小生成樹的時候記錄删邊即可。
那麼，我們隻需要每次取出滿足條件的最小邊權的邊，維護并查集即可。
時間複雜度：(O(n^2 + m)).（并查集的 (alpha leq 4) 被忽略）
期望得分：(70pts).
實際得分：(70pts) ~ (100pts).（取決于常數大小）
算法三
對于 (100 \%) 的資料，(N leq 10^4)，(M leq 10^5).
有了算法二的鋪墊，我們隻需要優化求 最小生成樹 的過程。
顯然，每次取出的邊一定要滿足 一個已經被選，一個未選，用哈希優化即可。（不需要用并查集了）
時間複雜度：(O(n log n + m)).（排序多出 (log)）
期望得分：(100pts)
實際得分：(100pts).
注（細節）：實際上我們隻需要記錄邊的資訊，不需要建圖。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
inline int read(){char ch=getchar();int f=1; while(!isdigit(ch)) {if(ch=='-')f=-f; ch=getchar();}
int x=0;while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
struct tree{
int start,end; //端點
int len; int xuhao; //邊權，原來的序号
};
tree a[N];
int n,m,s=0,p=0;
bool h[N]; //哈希
int ans[N]; //記錄答案
inline bool cmp(tree x,tree y){
return x.len<y.len;
} //結構體排序方式
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++) {
a[i].start=read(); a[i].end=read();
a[i].len=read(); a[i].xuhao=i;
}
sort(a+1,a+1+m,cmp); //存邊排序
/*s=a[1].len;*/ h[a[1].start]=h[a[1].end]=1;
printf("%d
",n-1); ans[++ans[0]]=a[1].xuhao; //取出第一條邊
for(int p=2;p<n;p++) //做 n-2 次
for(int i=2;i<=m;i++)
if(h[a[i].start]+h[a[i].end]==1) {
ans[++ans[0]]=a[i].xuhao; //記錄答案
h[a[i].start]=h[a[i].end]=1;
break; //找到最小的，結束
} sort(ans+1,ans+1+ans[0]); //排序，輸出答案
for(int i=1;i<=ans[0];i++) printf("%d
",ans[i]);
return 0;
}