P1546 最短網絡（最小生成樹）

題見洛谷

最小生成樹

prim 并點

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string> 
#include<algorithm>
using namespace std;
int tu[][],dis[],a[];
int main()
{
    //freopen("a.in","r",stdin);              

    memset(tu,,sizeof(tu));
    memset(dis,,sizeof(dis));
    int n;
    scanf("%d",&n);
    for(int i=;i<=n;i++)
     for(int j=;j<=n;j++)
    {
        int c;
        scanf("%d",&c);
        if(c==) c=;
        tu[i][j]=c;
        tu[j][i]=c;

    }
    int tot=;
    a[++tot]=;
    for(int i=;i<=n;i++) dis[i]=tu[][i];
    dis[]=;

    int ans=;
    while(tot<n)
    {
        int minl=,mink;
        for(int i=;i<=n;i++)
        {
            if(dis[i]<minl&&dis[i]) minl=dis[i],mink=i;
        }

        a[++tot]=mink;ans+=dis[mink];dis[mink]=;

        for(int i=;i<=n;i++)
         dis[i]=min(dis[i],tu[mink][i]);
    }
    //int ans=0;
    //for(int i=1;i<=n;i++)
    // ans+=dis[i];
    printf("%d",ans);
    return ;
}
           

克魯斯卡爾 并邊

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string> 
#include<algorithm>
const int MAX=;
using namespace std;
struct H{
    int x;
    int to;
    int v;
}a[*];


int v_comp(const H & a,const H & b)
{
    if(a.v<b.v) return ;
    return ;
}


int fa[],b[],n;
int findfather(int x)
{
    //if(fa[x]==x) return x;
    int k=x;
    while(fa[x]!=x)
     x=fa[x];
    return fa[k]=x;
}
int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++) fa[i]=i;
    int cnt=;
    for(int i=;i<=n;i++)
      for(int j=;j<=n;j++)
      {
          int k;
          scanf("%d",&k);
          if(k==) k=MAX;
          a[++cnt].x=i;
          a[cnt].to=j;
          a[cnt].v=k;
      }

    sort(a+,a+cnt+,v_comp);

    int tot=,ans=;


    for(int i=;i<=cnt;i++)
    {
        int f1=findfather(a[i].x),f2=findfather(a[i].to);
        if(f1!=f2) //一端在集合内，一端不在集合内 
        {
          //fa[a[i].x]=f1;fa[a[i].to]=f2;

          fa[f2]=f1;//路徑壓縮 
          ans+=a[i].v;
          tot++;
        }
        if(tot==n-) break;
    }

    printf("%d",ans);
    return ;
}