求點(diǎn)贊，求關(guān)注，小UP想變大UP的夢(mèng)想就靠你實(shí)現(xiàn)了！

最近新入了一個(gè)畫圖軟件，講講圖論再合適不過(guò)了

創(chuàng)新互聯(lián)建站"三網(wǎng)合一"的企業(yè)建站思路。企業(yè)可建設(shè)擁有電腦版、微信版、手機(jī)版的企業(yè)網(wǎng)站。實(shí)現(xiàn)跨屏營(yíng)銷，產(chǎn)品發(fā)布一步更新，電腦網(wǎng)絡(luò)+移動(dòng)網(wǎng)絡(luò)一網(wǎng)打盡，滿足企業(yè)的營(yíng)銷需求！創(chuàng)新互聯(lián)建站具備承接各種類型的網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)項(xiàng)目的能力。經(jīng)過(guò)十年的努力的開拓，為不同行業(yè)的企事業(yè)單位提供了優(yōu)質(zhì)的服務(wù)，并獲得了客戶的一致好評(píng)。引入

我們來(lái)看這樣一個(gè)東西

找到一棵樹，邊長(zhǎng)之和最小，也就是最小生成樹

一個(gè)一個(gè)選DFS，太慢了?

那怎么辦呢？

Kruscal

我們注意到，邊長(zhǎng)之和最小

那我們優(yōu)先選邊長(zhǎng)之和最小就可以了呀

但要選的是一棵樹，如果按這個(gè)想法，可能會(huì)有回路產(chǎn)生，那就不好了

我們之前講了并查集

想一下，可以用并查集嗎

我們看兩個(gè)點(diǎn)的最老的祖先節(jié)點(diǎn)，如果兩個(gè)是同一個(gè)點(diǎn)，就不能選了

我們的想法就好了

設(shè)每一條邊是x-y，長(zhǎng)度為k，我們按照k排序，如果兩個(gè)點(diǎn)x,y的最老的祖先節(jié)點(diǎn)一樣，那這條邊就不添加

我們來(lái)模擬一下樣例

選中的邊紅色，不能連的黃色，剩下最小的綠色，沒(méi)連的藍(lán)色

當(dāng)你連了點(diǎn)數(shù)N-1條邊，就是一顆最小生成樹

圖例1

最終的最小生成樹（這個(gè)圖不太好，沒(méi)有黃色的邊出現(xiàn)）

再來(lái)一個(gè)?

圖例2?

并查集告訴我們AC不能連

至此，最小生成樹產(chǎn)生了

原理講完了，我們看題

例1

登錄 - 沐楓OJhttps://www.mfstem.org/p/688可以說(shuō)模板題，沒(méi)啥好講的，代碼里有注釋講解，自己看吧

#includeusing namespace std;
#define int long long
int n,tp,f[10005],sum,ans;
struct road{//定義x,y,t
	int x;
	int y;
	int t;
}r[100005];
bool cmp(road a,road b){//排序
	return a.t< b.t;
} 
int fi(int x){
	return f[x] == x ? x : f[x] = fi(f[x]);//找最老的祖先
}
signed main(){
	cin >>n;
    for(int i = 1;i<= n;++i){
        f[i] = i;//注意初始化
        for(int j = 1,a;j<= n;++j){//讀入
            cin >>a;
            if(i< j){
                ++tp;
                r[tp].x = i,r[tp].y = j,r[tp].t = a;//添加邊
            }
        }
    }
	sort(r + 1,r + tp + 1,cmp);//排序
	for(int i = 1;i<= tp;++i){
		int q = fi(r[i].x),p = fi(r[i].y);//找最老的祖先
		if(q != p){
			++sum;
			f[q] = p;//認(rèn)“爸爸”
			ans += r[i].t;//加邊權(quán)
		}
		if(sum == n - 1){//滿足要求，退出
			cout<< ans<< endl;
			return 0;
		}
	}
	return 0;
}

練習(xí)：

登錄 - 沐楓OJhttps://www.mfstem.org/p/692我的AC代碼：

#includeusing namespace std;
#define int long long
int n,tp,f[2005],sum,ans,m;
struct road{
	int x;
	int y;
	int t;
}r[10005];
bool cmp(road a,road b){
	return a.t< b.t;
} 
int fi(int x){
	return ((f[x] == x) ? x : f[x] = fi(f[x]));
}
signed main(){
	cin >>n >>m;
    for(int i = 1;i<= n;++i)f[i] = i;
    for(int i = 1,p,xx,yx,tx;i<= m;++i){
        cin >>p >>xx >>yx >>tx;
        if(p == 1){
            ans += tx;
			int xxx = fi(xx),yyy = fi(yx);
            if(xxx != yyy)f[xxx] = yyy,++sum;
        }
        else{
            ++tp;
            r[tp].x = xx,r[tp].y = yx,r[tp].t = tx;
        }
    }
	if(sum >= n - 1){
		cout<< ans<< endl;
		return 0;
	}
	// cout<< tp<< endl;
	sort(r + 1,r + tp + 1,cmp);
	for(int i = 1;i<= tp;++i){
        // cout<< r[i].x<< " "<< r[i].y<< endl;
		int q = fi(r[i].x),p = fi(r[i].y);
		if(q != p){
			f[q] = p;
			ans += r[i].t;
			++sum;
			// for(int j = 1;j<= n;++j)cout<< f[j]<< " ";
			// cout<< endl;
		}
		if(sum == n - 1){
			cout<< ans<< endl;
			return 0;
		}
	}
	return 0;
}

代碼我就不解釋了，要做完才能看代碼喲

下期講講基礎(chǔ)A+B，敬請(qǐng)期待

拜了個(gè)拜！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：最小生成樹Kruscal算法（C++）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)于：http://aaarwkj.com/article14/ihgde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、Google、關(guān)鍵詞優(yōu)化、云服務(wù)器、營(yíng)銷型網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)