#include <fstream>
#include <iostream>
using namespace std;
struct myline{
int a,b;
};
int ok[100];
int father[100];
int inimap();
int n,d;
int map[100][100];
myline lines[10000];
int inimap()
{
ifstream fin("in.txt");
fin >>n;
d=0;
int i,j,k,l=0,min,minida,minidb;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
fin >>map[i][j];
if (i<j && map[i][j]>0)
{
d++;
lines[l].a=i;
lines[l].b=j;
l++;
}
}
}
myline tmp;
for (i=0;i<d;i++)
{
min=2000000;
for (j=i;j<d;j++)
{
if (map[lines[j].a][lines[j].b]<min)
{
min=map[lines[j].a][lines[j].b];
minida=j;
}
}
tmp=lines[i];
lines[i]=lines[minida];
lines[minida]=tmp;
}
for (i=0;i<d;i++){cout <<map[lines[i].a][lines[i].b]<<' ';}
cout <<endl;
for (i=0;i<n;i++)father[i]=-1;
return 0;
}
int find(int j)
{
if (father[j]==-1)return j;
int i;
i=find(father[j]);father[j]=i;return i;
}
int together(int j,int k)
{
if (find(j)==find(k))return 1;
return 0;
}
int thesame(int j,int k)
{
father[find(j)]=find(k);
return 0;
}
int main()
{
inimap();
int i,j,k,cost=0;
for (i=0;i<d;i++)
{
j=lines[i].a;k=lines[i].b;
if (!together(j,k))
{
thesame(j,k);cost+=map[j][k];
}
}
cout <<cost;system("pause");
return 0;
}
- 1
- 2
前往页