題目

一個圖，給幾條固定的邊，求最小生成樹

輸入

第一行n，m表示n個點，有m條邊，每行四個非負(fù)整數(shù)，p,u,v,w 當(dāng)p=1時，表示這個邊為固定邊（必須要）；當(dāng)p=2時，表示一條邊；u,v,w表示點u，v之間的邊，w表示權(quán)值。
5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5

輸出

最小生成樹的值和固定邊的值的和
9

---

解題思路

這道題用O(n log n)的算法，把固定邊鏈接的點看成同一個點。

---

代碼

#include<cstdio> #include<algorithm>//算法庫 using namespace std; struct wolf//表示一條線 {int cost,first,last; }; int n,h,k,s,w,x,y,q,lt[2001],num; wolf a[10001];//線 bool cmp(wolf x,wolf y) {return x.cost<y.cost; }//排序比較器 int father(int x) {if (lt[x]!=x) lt[x]=father(lt[x]);return lt[x];//找初始點（并查集） } void unionn(int x,int y) {int fa=father(x);int fb=father(y);if (fa!=fb) lt[fa]=fb; }//改變點 int main() {scanf("%d%d",&n,&h);for (int i=1;i<=n;i++) lt[i]=i;//初始化聯(lián)通分量for (int i=1;i<=h;i++){scanf("%d%d%d%d",&q,&x,&y,&w);if (q==1){unionn(x,y);//合并兩個點s+=w;//記錄固定邊的值}else{k++;a[k].cost=w;a[k].first=x;a[k].last=y;//邊}}sort(a+1,a+1+k,cmp);//排序for (int i=1;i<=k;i++){if (father(a[i].first)!=father(a[i].last))//如果聯(lián)通分量不一樣{s+=a[i].cost;//記錄權(quán)值num++;//記錄一條邊unionn(a[i].first,a[i].last);//合并}if (num==n-1) break;//如果邊數(shù)夠設(shè)則退出}printf("%d",s); }

總結(jié)

以上是生活随笔為你收集整理的ssl2346-联络员【图论，最小生成树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。