克鲁斯卡尔算法求最小生成树
这道题的难度不大,主要是因为有必选边.
其实可以在输入时就优先处理必选边.
剩下的就是常规的最小生成树了.
具体看代码注释.
时间复杂度 $O(nlogn)$
C++ 代码
#include<bits/stdc++.h>
#define N 2010
#define M 10010
using namespace std;
struct node{
int type,from,to,dis;//type记录当前边的类型,from记录当前边的起点,to记录当前边的终点,dis记录当前边的权值
}e[M];
int n,m,fa[N],k,tot;//k记录当前已选择了几条边,tot记录最终的权值
int find(int x)//并查集基本操作
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
inline void merge(int x,int y)//并查集基本操作
{
fa[find(y)]=find(x);
}
bool rule(const node &x,const node &y)//按边权从小到大排序
{
return x.dis<y.dis;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)//并查集初始化
fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%d %d %d %d",&e[i].type,&e[i].from,&e[i].to,&e[i].dis);
int type=e[i].type,u=e[i].from,v=e[i].to,d=e[i].dis;
if(type==1){//如果是必选边
tot+=d;//注意题目要求要加入所有的从u到v的必选边
if(find(u)!=find(v)){//当前两点不连通
merge(u,v);//合并
k++;//边数加一
}
}
}
sort(e+1,e+1+m,rule);
for(int i=1;i<=m;i++){//克鲁斯卡尔算法求最小生成树
if(k==n-1)
break;
int type=e[i].type,u=e[i].from,v=e[i].to,d=e[i].dis;
if(type==1)//必选边已经处理了,直接跳过
continue;
if(find(u)!=find(v)){
merge(u,v);
tot+=d;
k++;
}
}
printf("%d\n",tot);
return 0;//完结撒花
}