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;
}