最小生成树

Prim算法(与Dijkstra算法非常像)

朴素版Prim O(n^2)

1. 初始化：dis[i]->正无穷.
2. for(int i=0;i<n;i++) 找到集合外最近的点.
3. 用t 更新其他点到 集合 的距离(Dijkstra算法是用t更新其他点到起点的距离).

#include<bits/stdc++.h>
using namespace std;

const int N=1010,INF=0x3f3f3f3f;

int dis[N],g[N][N],n,m;
bool st[N];

int Prim()
{
  //若图不连通返回INF,否则返回res;
  memset(dis,INF,sizeof(dis));
  int res=0;

  for(int i=0;i<n;i++)//迭代n次(而Dijkstra算法中为：for(int i=1;i<=n-1;i++))
  {
    int t=-1;
    for(int j=1;j<=n;j++)
    {
      if(!st[j]&&(t==-1||dis[j]<dis[t]))
      {
        t=j;
      }
     }
      if(i&&dis[t]==INF) return INF;
      if(i) res+=dis[t];
      st[t]=true;
    for(int j=1;j<=n;j++) dis[j]=min(dis[j],g[t][j]);
  }


 return res;
}
int main()
{
  scanf("%d%d",&n,&m);

  for(int i=1;i<=n;i++)//初始化
  {
    for(int j=1;j<=n;j++)
    {
      if(i==j) g[i][j]=0;
      else g[i][j]=INF;
    }
  }

  while(m--)
  {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    g[a][b]=g[b][a]=min(g[a][b],c);
  }

  int t=Prim();
  if(t==INF) puts("impossible");
  else printf("%d\n",t);

  return 0;
}