思路：將邊排序，依次向并查集里加邊，并且保證此邊連接的兩個結點不在一個并查集里，加到N-1（N為圖中結點數）條邊時，就生成了最小生成樹
#include<iostream> #include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;int ecnt;struct node{int from,to,value;} edge[100001];void add(int from,int to,int value){ ecnt++; edge[ecnt].from=from; edge[ecnt].to=to; edge[ecnt].value=value;}int fath[100001];int getfath(int x){ if(fath[x]==x) return x; return fath[x]=getfath(fath[x]);}void unionset(int x,int y){fath[getfath(x)]=getfath(y);}int cmp(const node &a,const node &b){ if(a.value<b.value) return true; else return false;}long long mstv=0,biancnt=0;int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; int from,to,value;int x; for(int i=1;i<=m;i++) { cin>>from>>to>>value; add(from,to,value); } for(int i=1;i<=n;i++) fath[i]=i; sort(edge+1,edge+ecnt+1,cmp); for(int i=1;i<=m;i++) { if(getfath(edge[i].from)!=getfath(edge[i].to)) { unionset(edge[i].from,edge[i].to); mstv+=edge[i].value; biancnt++; } if(biancnt==n-1) break; } cout<<mstv; return 0;}所謂的Slim Span即為最大邊與最小邊差值最小的生成樹，與最小生成樹問題的思路相似
先對邊升序排序，對于一個連續的邊區間
新聞熱點
疑難解答
