[ 登录注册 ]

研发管理

C++最小生成树问题

2016-08-25 22:11:00 admin 返回上一页

问题描述
求一个连通无向图的最小生成树的代价(图边权值为正整数)。
输入
第一行是一个整数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;
}

文章来源:http://www.bozhiyue.com/software/2016/0825/433273.html
返回上一页    返回分类 上一篇:   下一篇:
相关