AcWing 1143. 联络员
原题链接
简单
作者:
楚天
,
2020-10-20 16:37:47
,
所有人可见
,
阅读 451
对于两种类型的边,我们分开考虑,
对于类型是1的边,我们直接ans+=他的权值,并用并查集维护
对于类型是2的边,我们做一遍kauskal,
那会不会有答案更小的情况呢?
不会的,因为我们有并查集维护连通性呀hh~
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,m;
int fa[N];
int ans=0;
struct node{
int a,b,c;
}e[N];
int cnt;
int find(int x)
{
if(fa[x]==x) return fa[x];
return fa[x]=find(fa[x]);
}
int kru()
{
int res=0;
for(int i=1;i<=cnt;i++)
{
int u=find(e[i].a);
int v=find(e[i].b);
if(u!=v)
{
res+=e[i].c;
fa[u]=v;
}
}
return res;
}
bool cmp(node a,node b)
{
return a.c<b.c;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
int opt,a,b,c;
cin>>opt>>a>>b>>c;
if(opt==1)
{
ans+=c;
fa[find(a)]=find(b);
}
else {
e[++cnt]={a,b,c};
}
}
sort(e+1,e+1+cnt,cmp);
cout<<ans+kru()<<endl;
}