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