RQNOJ193 造路行动

冷不防 2021-11-01 12:22 266阅读 0赞

[**题目转移**][Link 1]

[**详见最小生成树讲解**][Link 2]

**Kruskal**

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=1005;
    int n,m,ans;
    int fa[maxn];
    struct edge{
        int x,y,v;
    }e[maxn*maxn];
    int find(int x)  //查找父亲节点 
    {
        if(fa[x]==x) return x;
        return fa[x]=find(fa[x]);
    }
    bool cmp(struct edge a,struct edge b)
    {
        return a.v<b.v;
    }
    void kruskall()
    {
        int cnt=0;
        sort(e+1,e+m+1,cmp);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=m;i++)
        {
            if(cnt==n-1) break;        
            int fx=find(e[i].x);
            int fy=find(e[i].y);
            if(fx!=fy)    
            {
                fa[fx]=fy;     //合并两棵树 
                cnt++;
                ans+=e[i].v;
            }        
        }
        printf("%d",ans);
    }
    int main()
    {
        int x,y,a;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++) 
        {
            scanf("%d%d%d",&x,&y,&a);
            e[i].x=x;
            e[i].y=y;
            e[i].v=a;            
        }
        kruskall();
        return 0;
    }

**Prim**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=1005;
    int n,m,ans,cnt=1;
    int fa[maxn],head[maxn],dis[maxn],vis[maxn];
    struct edge{
        int x,y,v,next;
    }e[maxn*maxn];
    
    void addedge(int x,int y,int a)//邻接矩阵
    {
        e[cnt].x=x;
        e[cnt].y=y;
        e[cnt].v=a;
        e[cnt].next=head[x];
        head[x]=cnt++;
    }
    void primm()
    {
        int mi;
        memset(dis,inf,sizeof(dis));
        dis[1]=0;
        int u;
        for(int i=1;i<=n;i++)
        {
            mi=inf;
            for(int j=1;j<=n;j++)
                if(!vis[j]&&mi>dis[j]) 
                {
                    mi=dis[j];u=j;    
                }
            vis[u]=1;
            ans+=mi;
            for(int k=head[u];k!=-1;k=e[k].next)
            {
                if(dis[e[k].y]>e[k].v)
                    dis[e[k].y]=e[k].v;
    
            }
            
        }
        printf("%d",ans);
    }
    int main()
    {
        int x,y,a;
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        for(int i=1;i<=m;i++) 
        {
            scanf("%d%d%d",&x,&y,&a);
            addedge(x,y,a);    
            addedge(y,x,a);        
        }
        primm();
        return 0;
    }

谢谢大家。

转载于:https://www.cnblogs.com/mzyczly/p/11028994.html

[Link 1]: http://www.rqnoj.cn/problem/193
[Link 2]: https://www.cnblogs.com/mzyczly/p/11025043.html