真爱无限的知识驿站

问题描述

求一个连通无向图的最小生成树的代价（图边权值为正整数）。

输入

第一行是一个整数N（1<=N<=20），表示有多少个图需要计算。以下有N个图，第i图的第一行是一个整数M（1<=M<=50），表示图的顶点数，第i图的第2行至1+M行为一个M*M的二维矩阵，其元素ai,j表示图的i顶点和j顶点的连接情况，如果ai,j=0，表示i顶点和j顶点不相连；如果ai,j>0，表示i顶点和j顶点的连接权值。

输出

每个用例，用一行输出对应图的最小生成树的代价。

样例输入

1

6

0 6 1 5 0 0

6 0 5 0 3 0

1 5 0 5 6 4

5 0 5 0 0 2

0 3 6 0 0 6

0 0 4 2 6 0

样例输出

15

‍‍分析：‍‍

   很明显，这是一个无向图，因为我们看到这个矩阵，它是对称的。

=>我们取它的左下角元素来进行操作，代码里就是让行 i 大于列 j.

=>存在结构体里面，按边的长度由小到大排序。

=>因为有n个顶点，所以我们要记录它各个顶点的值，来判断两个顶点之间是不是已经有边连接。

下面说一下分析步骤：

我的由输入得到这个图：

从长度由小到大连接，符合条件（a[i]不等于a[j]）的就操作，其它的不操作:

每一步都要把值与左边的值相同的全设置为右边的数：

两端数值相等就不要操作了。

最后把符合条件的边的长度加起来就是我们求的最小生成树的代价。

代码：

#include<iostream>
using namespace std;
struct node 
{
 int l;
 int r;
 int len;
 node *next;
};
void insert(node *&h,node *p)   //指针插入排序
{
 node *q=h;
 while(q->next && q->next->len <= p->len)
 {
  q=q->next;
 }
 p->next=q->next;
 q->next=p;
}
int main()
{
// freopen("001.in","r",stdin);
 node *h,*p;
 int n,m,x,temp;
 int *a;
 int i,j;
 int sum;
 cin>>n;
 while(n--)
 {
  sum=0;
  cin>>m;
  a=new int[m+1];
  for (i=1;i<=m;i++)
  {
   a[i]=i;
  }
  h=new node;
  p=h;
  p->next=NULL;
  for (i=1;i<=m;i++)
   for (j=1;j<=m;j++)
   {
    cin>>x;
    if (i>j && x!=0)
    {
     p=new node;
     p->l=i;
     p->r=j;
     p->len=x;
     p->next=NULL;
     insert(h,p);   //调用插入排序
    }
   }
          p=h->next;
   while (p)
   {
    if (a[p->l]!=a[p->r])
    {
     
     sum+=p->len;
     temp=a[p->l];
     for(i=1;i<=m;i++)
      if (a[i]==temp)
      {
       a[i]=a[p->r];
      }
    }
   p=p->next;
   }
   /*   可以测试程序工作是否正常
   p=h->next;
   while(p)
   {
    cout<<p->l<<':';cout<<p->r<<' ';
    cout<<p->len<<"   ";
    p=p->next;
   }
   */
   cout<<sum<<endl;   
 }
 return 0;
}