最小生成树

首先，生成树是指在一个连通图中的连通子图，hanyou图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。

而最小生成树则是指在连通网的所有生成树中，所有的代价和最小的生成树。

Kruskal算法

思路：初始边数为1，每迭代一次就选择最小（或者最大，看题目要求），加入到最小生成树的边集合中。

实现步骤：

1.把图中所有边按照权值从大到小（或从小到大）排序。

2.把图中的n个顶点看成独立的n棵组成的集合。

3.按照排序的权值排边，所选的边连接的两个顶点应属于两颗不同的数，（如用的并查集即两个顶点的父亲节点不同），则成为最小生成树的一条边，并且将着两棵树合并成一棵树。重复此步骤直到所有顶点都在一颗数内或者有n-1条边为止。

接下来通过题目理解：

并查集实现

题目链接：传送门

下边有模板题的传送门。

题目：

又到了一年一度的明明生日了，明明想要买 $B$ 样东西，巧的是，这 $B$ 样东西价格都是 $A$ 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 $I$ 样东西，再买第 $J$ 样，那么就可以只花 $K_{I,J}$ 元，更巧的是， $K_{I,J}$ 竟然等于 $K_{J,I}$ 。

现在明明想知道，他最少要花多少钱。

输入：

第一行两个整数， $A, B$ 。

接下来 $B$ 行，每行 $B$ 个数，第 $I$ 行第 $J$ 个为 $K_{I,J}$ 。

我们保证 $K_{I,J}=K_{J,I}$ 并且 $K_{I,I}=0$ 。

特别的，如果 $K_{I,J}=0$ ，那么表示这两样东西之间不会导致优惠。

输出：

一个整数，为最小要花的钱数。

通过题目不难看出，当买了一件商品后另一件产品将可能以低价售出，这样我们就可以把每个礼物看成一个顶点，将一件产品与买过这件产品后会降价的产品连接起来，权值为降价后商品的价格。然后用最小生成树遍历一遍即可。

但仔细想一下，入度为零的顶点产品的价格又要怎么存储呢？这里就要用上一个小技巧：即每一条边从0开始连接，那么与0相连的权值自然就是入度为0的产品的价格了。

上代码：

#include
using namespace std;
const int maxn=300000;
int a,b,k,f[maxn],ans;
struct node{
    int u,v,w;
}t[maxn];//结构体存边与权值。
int find(int x)
{
    if(x==f[x])
        return x;
    return f[x]=find(f[x]);
}
bool cmp(node A,node B)
{
    return A.wb)//如果所需每个顶点都遍历过了直接退出。
            break;
        if(find(t[i].u)!=find(t[i].v)){//步骤三核心思想.
            cnt++;
            ans+=t[i].w;
            to(t[i].u,t[i].v);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>a>>b;
    for(int i=1;i<=b;i++){
        for(int j=1;j<=b;j++){
            int op;
            cin>>op;
            if(i



Prim算法
思路：每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

图的所有顶点集合为VV；初始令集合u={s},v=V?uu={s},v=V?u;
在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

模板题传送门
模板题就不贴题目了。
#include
using namespace std;
int n,m,ans,cnt,k,dis[5005],check[5005],head[200002];
struct node{
    int to,w,next;
}e[400004];
void add(int u,int v,int w)
{
    e[k].to=v;
    e[k].w=w;
    e[k].next=head[u];
    head[u]=k++;
}
typedef pairP;
priority_queue,greater>q;
void prim()
{
    dis[1]=0;
    q.push({0,1});
    while(!q.empty()&&cnt>n>>m;
    memset(dis,127,sizeof(dis));
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    prim();
    if(cnt==n)
        cout<

最小生成树

Kruskal算法

相关

标签