最小生成树

概念

最小生成树即为无向图中结点构成的树中各边权值之和最小的树，可以有多种情况。一般用Kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。

Kruskal算法

方法

可以将Kruskal算法理解成对边的贪心算法。

1.将路径用邻接表存储，存储的值为起点、终点和权值；
2.将邻接表按照权值为关键字排序；
3.从最小权值的边开始循环，每连接起两个结点就把它们并到同一个集合（并查集实现），连接之前判断它们是否已经直接或间接相连（是否同一祖先），如没有相连则连上；
4.判断能否构成树：如果所以结点的祖先相同则能，反之则不能构成树。

代码及注解

示例题目：洛谷 P3366 【模板】最小生成树

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,a,b,c,k,ans;
int f[5005];
struct lj{
    int qi,zhong,zhi;
};//邻接表存储
lj map1[200005];
bool com(lj a,lj b)
{
    return a.zhi>b.zhi;
}//以权值为关键字排序
int zx(int a)
{
    if(a==f[a]) return a;
    else 
    {
        f[a]=zx(f[a]);
        return f[a];
    } 
}//并查集查找祖先
int main()
{
    cin>>n>>m;
    for (a=1;a<=n;a++)
    f[a]=a;
    for (a=1;a<=m;a++)
    {
        cin>>x>>y>>z;
        map1[a].qi=x;
        map1[a].zhong=y;
        map1[a].zhi=z;
    }
    sort(map1,map1+m+1,com);//排序
    while (m>0)
    {
        x=map1[m].qi;
        y=map1[m].zhong;
        if (zx(x)!=zx(y)) //查找祖先以确定是否相连
        {
            f[zx(y)]=zx(x);//连接，统一祖先
            ans+=map1[m].zhi;//加上权值
        }
        m--;
    }
    for (a=2;a<=n;a++)
    if (zx(a)!=zx(1))
    {
        cout<<"orz";
        return 0;
    }//判断能否构成树，只有每一个结点祖先和第一个结点祖先相同，则所有结点祖先都相同
    cout<<ans;
    return 0;
}

upd:2018.10.23 今天来把这个大半年的坑给填了。咕咕咕

Prim算法

方法

每次找到与当前点连接的点中权值最小且没被查找过的点进行拓展，记录一下当前点是否已经被查找过，如果全部查找完了就结束了。

过程和Dijkstra算法的堆优化写法很像，可以用一个优先队列来维护队列中权值最小的点，然后BFS即可。

代码

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge{
    int next,to,w;
} edge[400005];
int n,m,a,b,c,cnt,ct,head[5005],ans,mn[5005];
bool vis[5005];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void prim()
{
    priority_queue <pr,vector<pr>,greater<pr> > q;
    q.push(mp(0,1));
    for (int i=1;i<=n;i++) mn[i]=1e9;
    mn[1]=0;
    memset(vis,0,sizeof(vis));
    while (!q.empty() && ct<n)
    {
        int x=q.top().second,qf=q.top().first; q.pop();
        if (vis[x]) continue;
        ans+=qf;
        ct++;
        vis[x]=1;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=edge[i].w;
            if (w<mn[y])
            {
                mn[y]=w;
                q.push(mp(mn[y],y));
            }
        }
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
        add(b,a,c);
    }
    prim();
    if (ct==n) printf("%d",ans);
    else printf("orz");
    return 0;
}

感觉自己码风变化真大，寒假的时候还是太naive了。