用prim和kruskal算法求最小生成树问题

目录

1.最短网络

2.局域网

3.繁忙的都市

4.联络员

5.连接格点

---

prim算法就类似与dijkstra算法从1号点到其他点的最短距离

kruskal算法是先按照边权排序，假如这条边的两个点不连通就加上这条边，假如连通了就跳过

1.最短网络

1140. 最短网络 - AcWing题库

#include
using namespace std;
const int N=110;
int w[N][N];
bool st[N];
int dist[N];
int n,res=0;
void prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;//初始化第一个点到自己的距离为0
    for(int i=1;i<=n;i++)//找剩下的n个点与第一起点的距离，就像dijkstra一样
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))//找不在连通块且距离最小的点
                 t=j;
        st[t]=true;//标记这个点在连通块内
        res+=dist[t];
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],w[t][j]);//用该点更新其他点的最短距离
    }
}
int main()
{
   cin>>n;
   for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
         cin>>w[i][j];
   prim();
   cout<
	return 0;
}

2.局域网

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

相当于一个图中求最小生成树的问题

prim解决

#include
using namespace std;
const int N=110;
int w[N][N];
bool st[N];
int dist[N];
int n,res=0,m;
void prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;//初始化第一个点到自己的距离为0
    for(int i=1;i<=n;i++)//找剩下的n个点与第一起点的距离，就像dijkstra一样
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))//找不在连通块且距离最小的点
                 t=j;
        st[t]=true;//标记这个点在连通块内
        res+=dist[t];
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],w[t][j]);//用该点更新其他点的最短距离
    }
}
int main()
{
    int ans=0;
   cin>>n>>m;
   memset(w,0x3f,sizeof w);
   while(m--)
   {
      int a,b,c;
      cin>>a>>b>>c;
      w[a][b]=w[b][a]=min(w[a][b],c);
      ans+=w[a][b];//记录所有网线的答案
   }
   prim();
   cout<//输出总的减最小生成数的
	return 0;
}

kruskal解决

#include
using namespace std;
const int N=110,M=N*N;
int n,m;
struct Edge
{
    int a,b,w;
    bool operator < (const Edge&t)const//重载小于号，待会排序就按照w排序
    {
        return w
    }
}e[M];//结构体存数
int p[N];
int find(int x)//并查集
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
   int ans=0;
   cin>>n>>m;
   for(int i=1;i<=n;i++) p[i]=i;//并查集初始化
   for(int i=0;i
   {
       int a,b,w;
       cin>>a>>b>>w;
       e[i]={a,b,w};
   }
   sort(e,e+m);//先排序
   for(int i=0;i
   {
       int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
       if(a!=b) p[a]=b;//假如不在一个集合，则加上该条边
       else ans+=w;//反之该条边就是多余不要的加上答案里
   }
   cout<//输出总的减最小生成数的
	return 0;
}

3.繁忙的都市

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

#include
using namespace std;
const int N=310,M=N*N;
struct Edge
{
    int a,b,w;
    bool operator < (const Edge&t) const//重载小于号，使排序按照w排
    {
        return w
    }
}e[M];
int p[N];
int find(int x)//并查集
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
   int n,m,ans;
   cin>>n>>m;
   for(int i=0;i
   {
       int a,b,w;
       cin>>a>>b>>w;
       e[i]={a,b,w};
   }
   for(int i=1;i<=n;i++) p[i]=i;//并查集初始化操作
   sort(e,e+m);//排序
   for(int i=0;i
   {
       int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
       if(a!=b)//假如不在一个连通块中，则加上他
       {
           p[a]=b;
           ans=w;//更新最大值
       }
   }
   cout<-1<<' '<
	return 0;
}

4.联络员

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

这题只能用kruskal，因为有多个连通块，而prim只能处理一个连通块

#include
using namespace std;
const int N=2010,M=1e4+10;
int res=0;
struct Edge
{
    int a,b,w;
    bool operator <(const Edge&t)const//重载小于号
    {
        return w
    }
}e[M];
int p[N];
int find(int x)//并查集
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
  int n,m,cnt=0;
  cin>>n>>m;
  for(int i=1;i<=n;i++) p[i]=i;//初始化
  for(int i=0;i
  {
      int t,a,b,w;
      cin>>t>>a>>b>>w;
      if(t&1)//假如是必选
      {
          res+=w;//则加上边权
          a=find(a),b=find(b);
          p[a]=b;//加到同一个连通块中
      }
      else e[cnt++]={a,b,w};//否则非必选
  }
  sort(e,e+cnt);//排序
  for(int i=0;i
  {
      int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
      if(a!=b)//假如不在一个连通块
      {
          res+=w;//则加上边权
          p[a]=b;//加到同一个连通块中
      }
  }
  cout<
	return 0;
}

5.连接格点

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

就是给你已经连接了的点，让你加上某些边使他连通，也就是最小生成树，但是不能用prim，可能给出的边有环，只能用kruskal

#include
using namespace std;
const int N=1010,M=N*N,K=2*M;
int ids[N][N];//用来将坐标映射到点
int n,m,k;
struct Edge
{
    int a,b,w;
}e[K];
int p[M];
int find(int x)//并查集
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
void edge()
{
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},dw[4]={1,2,1,2};//四个方向
    for(int s=0;s<2;s++)//s表示余数，0表示打横走，1表示纵着走
        for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
             for(int u=0;u<4;u++)
                if(u%2==s)//走的途径
               {
                    int x=i+dx[u],y=j+dy[u],w=dw[u];
                    if(x<=0||x>n||y<=0||y>m) continue;//假如越界
                    int a=ids[i][j],b=ids[x][y];//获取当前位置
                    if(a//为了避免重复假如
               }
}
int main()
{
  cin>>n>>m;
  for(int i=1;i<=n*m;i++) p[i]=i;//初始化
  for(int i=1,t=1;i<=n;i++)//映射坐标为点
    for(int j=1;j<=m;j++,t++)
        ids[i][j]=t;
  int x1,x2,y1,y2;
  while(cin>>x1>>y1>>x2>>y2)
  {
      int a=ids[x1][y1],b=ids[x2][y2];
      p[find(a)]=find(b);//假如是连通块了，则加到同个连通块中
  }
  edge();//处理每个走的方式
  int res=0;
  for(int i=0;i
  {
      int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
      if(a!=b)//假如不在一个连通块
      {
          res+=w;//则加上边权
          p[a]=b;//加到同一个连通块中
      }
  }
  cout<
	return 0;
}