目錄

題目：村村通

并查集?

題目：最小生成樹

kruskal算法

prim算法

????????

先引入問題：

要在n個城市之間鋪設(shè)光纜，主要目標(biāo)是要使這 n 個城市的任意兩個之間都可以通信，但鋪設(shè)光纜的費用很高，且各個城市之間鋪設(shè)光纜的費用不同，因此另一個目標(biāo)是要使鋪設(shè)光纜的總費用最低。這就需要找到帶權(quán)的最小生成樹。

說白了就是將此圖連通起來的最小代價。

????????

對于一個有N個點的圖，邊一定是大于等于N-1條的。圖的最小生成樹，就是在這些邊中選擇N-1條出來，連接所有的N個點。這N-1條邊的邊權(quán)之和是所有方案中最小的

有兩種算法：prim和kruskal

前者適合稠密圖，后者適合稀疏圖(不然炸你內(nèi)存)

????????

????????

要先說并查集才行

題目：村村通

????????

并查集?

【并查集思想】：是集合。一個是并操作(建樹)，一個是查操作(查樹)。并操作是將一個集合的樹變成另一個集合樹的子樹。

????????
我們只需要建和原圖等價的并查樹即可，根本不用建原圖
查操作是從該元素開始查找父節(jié)點直到找到根節(jié)點看看是否相同

????????
1，初始化每個點的父親為自身
2，并操作：(建邊)合并兩個集合的樹根(祖宗)（查的過程中并路徑壓縮）
3，查操作：最后查找有幾個祖宗即可

#include <bits/stdc++.h>              
using namespace std;
int fa[1000001], n, m, x, y;
int find(int x)
//找到祖先后并修改中間點的fa（路徑壓縮使更快的查到祖宗，
//其實就是對樹進行優(yōu)化，減少了樹的深度，效果是將多代變成一代） 
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
//自己不是祖宗，直接更新成親爹的祖宗號
//但是如果是dp，那就要先保存原親爹號，不然你就找不到爹了（路徑壓縮的代價）
    return fa[x];//返回祖先 
}
void unity(int x, int y)
{
    int f1=find(x);//如果x和y本來就在同一個集合完全 不影響
    int f2=find(y);
    fa[f1]=f2;//合并樹根 
}
int main()
{
	while(true)
	{
		int ans=0;
		cin>>n>>m;
		if(n==0) return 0;
	    for(int i=1; i<=n; i++){
	    	fa[i]=i;//先初始化成節(jié)點
		}
	    for(int i=1; i<=m; i++){
	    	scanf("%d %d", &x, &y);//合并<x,y>能到的地方
	        unity(x,y);//建邊,建樹
		}
	    for(int i=1; i<=n; i++){//一共有幾個祖宗
	    	if(find(i)==i) ans++;
		}
		printf("%d\n", ans-1);//共需修ans-1條路即可
	}
    return 0;
}

?????????

?????????

題目：最小生成樹

?????????

kruskal算法

【kruskal】：貪心的每次取最小權(quán)值的邊進行合并（只要不構(gòu)成環(huán)），當(dāng)恰好合并了n-1條邊時候就是最小生成樹。只要小于就不是，此圖也不連通
可以使用并查集來實現(xiàn)合并和不構(gòu)成環(huán)

????????????????
kruskal甚至不需要建圖，但是如果是完全圖的話，存邊容易MLE，這時候就要prim

#include<bits/stdc++.h>
using namespace std;
int f;
struct Edge{ int u,v,w; }e[200005];
int fa[5005],n,m,ans,cnt;

bool cmp(Edge a,Edge b){ return a.w<b.w;}

int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];//返回祖先 
}

void kruskal()
{
    sort(e+1,e+1+m,cmp);//將邊的權(quán)值排序
    for(int i=1;i<=m;i++)
    {
        int fu=find(e[i].u), fv=find(e[i].v);
        if(fu==fv) continue;  //若出現(xiàn)兩個點已經(jīng)聯(lián)通了，則說明這一條邊不需要了
        ans+=e[i].w; //將此邊權(quán)計入答案
        fa[fv]=fu; //合并操作
        if(++cnt==n-1)//如果邊數(shù)恰好為n-1，則說明最小生成樹已經(jīng)建成
        {
            f=1;break;
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;//初始化并查集節(jié)點
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
    }
    kruskal();
    if(f==1)printf("%d",ans);
    else cout<<"orz";//不連通
    return 0;
}

?????????

prim算法

【prim算法】：prim算法基于貪心，我們每次總是選出一個離生成樹距離最小的點去加入生成樹，最后實現(xiàn)最小生成樹（不做證明，理解思想即可）

每次都最小生成數(shù)和dijkstra思想很像，都是從小圖開始，每次都從周圍合并一個最小的點然后不斷擴大，所以長得也很像，感覺完全一樣啊文章來源地址http://www.zghlxwxcb.cn/news/detail-759236.html

#include <bits/stdc++.h>
using namespace std;
int k,n,m,cnt,sum;
int head[5005],dis[5005],vis[5005];
typedef pair <int,int> pii;
struct Edge{ int v,w,next;}e[400005];

void add(int u,int v,int w){e[++k]=(Edge){v,w,head[u]};head[u]=k;}

void prim()
{
	priority_queue <pii,vector<pii>,greater<pii> > q;
	memset(dis,0x3f,sizeof(dis));
    dis[1]=0;//dis是周圍點到集合的最小距離
    q.push(make_pair(0,1));
    while(!q.empty()&&cnt<n)//cnt是已經(jīng)加入的點數(shù)
    {
        int d=q.top().first,u=q.top().second;//取出周圍最小dis的點
        q.pop();
        if(vis[u]) continue;
        cnt++;
        sum+=d;
        vis[u]=1;//標(biāo)記此點已經(jīng)加入
	    for(i=head[u];i;i=e[i].next){
	        int ve=e[i].v,vw=e[i].w;//到集合最小距離就是權(quán)值
	        if(vw<dis[ve])//如果變小就更新入隊，以便獲取最小的點
	            dis[ve]=vw,q.push(make_pair(dis[ve],ve));
	    }
    }
}

int main()
{
	int u,v,w;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    prim();
    if (cnt==n)printf("%d",sum);
    else printf("orz");//如果小于n說明不連通
}

到了這里，關(guān)于【算法每日一練]-圖論（保姆級教程篇7 最小生成樹 ，并查集模板篇）#村村通 #最小生成樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！