最小生成树链式前向星？
老哥 $ nb $
by Cesare @ 2019-03-04 13:43:34
@[Cesare](/space/show?uid=104379) 承让哈哈一时激动qwq
by 良辰、 @ 2019-03-04 13:45:11
@[良辰、](/space/show?uid=50604) $ but $这题好像并不需要连双向边把
by Cesare @ 2019-03-04 13:46:48
@[Cesare](/space/show?uid=104379) 连单向边了之后也不对qwq
by 良辰、 @ 2019-03-04 13:48:12
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000010;
struct qaq{
int next,to,val,pre;
}tree[maxn];
int l,r,w;
int n,m,k,sum,ans;
int head[maxn],cnt;
int f[maxn];
void add(int l,int r,int w){
cnt++;
tree[cnt].to=r;
tree[cnt].val=w;
tree[cnt].pre=l;
tree[cnt].next=head[l];
head[l]=cnt;
}
int find(int x){
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
bool cmp(qaq a,qaq b){
return a.val<b.val;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&l,&r,&w);
add(l,r,w);
}
sort(tree+1,tree+1+m,cmp);
for(int i=1;i<=m;i++){
int fx=find(tree[i].pre);
int fy=find(tree[i].to);
if(fx!=fy){
f[fx]=fy;
sum++;
ans+=tree[i].val;
}
if(sum==n-k){
cout<<ans<<endl;
return 0;
}
}
puts("No Answer");
return 0;
}
```
by 二哥喝可乐 @ 2019-03-04 13:49:15
next指的是下一条边的编号，会wei的
by 二哥喝可乐 @ 2019-03-04 13:49:57
@[Cesare](/space/show?uid=104379) （捕捉
by 派大那个星 @ 2019-03-04 13:50:15
@[良辰、](/space/show?uid=50604) 你的$head$没啥用啊...找爹的应该是$l,r$。
by Cesare @ 2019-03-04 13:50:29
@[违规用户名SpChFZJO](/space/show?uid=94518) 感谢dalao（我可能还是没有理解透链式前向星qwq
by 良辰、 @ 2019-03-04 13:50:56
加入一条边进入最小生成树的时候是判断，边的起点和终点是否为统一集合
by 二哥喝可乐 @ 2019-03-04 13:50:57