如果某条边是跨越集合且边权最小的边, 那么所有最小生成树一定经过它,
而回路上边权最大的边, 所有最小生成树一定不经过它
最小生成树有 Prim 算法, 适用于稠密图, 时间复杂度 O(n^2)(优化后 O(nlogn), 不如 Kruskal 方便)
下面是 Kruskal 算法模板:
- bool operator <(rec a,rec b){
- return a.z<b.z;
- }
- IN int get(int x){
- if(x==fa[x]) return x;
- return fa[x]=get(fa[x]);
- }
- int main(){
- int n,m,ans=0,cnt=0;
- scanf("%d %d",&n,&m);
- REP(i,1,m)
- scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].z);
- sort(edge+1,edge+1+m);
- REP(i,1,n) fa[i]=i;
- REP(i,1,m){
- int x=get(edge[i].x),y=get(edge[i].y);
- if(x==y) continue;
- fa[x]=y;
- ans+=edge[i].z;
- cnt++;
- if(cnt==n-1) break;
- }
- if(cnt!=n-1) printf("orz");
- else printf("%d",ans);
- View Code
来源: http://www.bubuko.com/infodetail-2530681.html