现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N(≤)和候选道路数目M(≤);随后的M行对应M条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出−,表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12
#include<iostream>
#include "string.h"
using namespace std;
#define MAX 1005
const int inf=999999;
int G[MAX][MAX];
int Top;
int k;
int Prime()
{
int sum=0;
int Lowcost[MAX];
memset(Lowcost,0,sizeof(Lowcost));
int i,j;
for(i=1; i<=Top; i++)
{
Lowcost[i]=G[1][i];
}
Lowcost[1]=-1;
for(i=1; i<Top; i++)
{
int min=inf,k=-1;
for(j=1; j<=Top; j++)
{
if(Lowcost[j]<min && Lowcost[j]!=-1 )
{
min=Lowcost[j];
k=j;
}
}
if(k!=-1)
{
sum+=Lowcost[k];
Lowcost[k]=-1;
for(j=1; j<=Top; j++)
{
if(G[k][j]<Lowcost[j])
{
Lowcost[j]=G[k][j];
}
}
}
}
for(i=1; i<=Top; i++)
if(Lowcost[i]!=-1)
break;
if(i<=Top)
return -1;
return sum;
}
int main()
{
int i, j, m, n;
int x,y,w;
cin >> m >> n;//m=顶点的个数,n=边的个数
if(m<=0)
{
cout<<"-1"<<endl;
return 0;
}
for(i=1; i<=m; i++)
for(j=1; j<=m; j++)
if(i==j) G[i][j]=0;
else G[i][j]=inf;
Top=m;
for(i=0; i<n; i++)
{
cin>>x>>y>>w;
G[x][y]=w;
G[y][x]=w;
}
cout<<Prime()<<endl;
return 0;
}
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int Max=1005;
int Father[Max];
struct Node
{
int priority;
int next;
int weight;
} A[3005];
bool Com(Node X,Node Y)
{
return X.weight<Y.weight;
}
int Find(int x) //²é
{
if(x==Father[x])
return x;
else
return Find(Father[x]) ;
}
bool Union(int x,int y) //²¢
{
int dx,dy;
dx=Find(x);
dy=Find(y);
if(dx!=dy)
{
Father[dx]=dy;
return true;
}
return false;
}
int main()
{
int m,n;
cin>>m>>n; // Top, Edge
int i;
for(i=1; i<=m; i++)
{
Father[i]=i;
}
for(i=1; i<=n; i++)
{
cin>>A[i].priority>>A[i].next>>A[i].weight;
}
sort(A,A+n,Com);
int count=m;
int sum=0;
for(i=1; i<=n && count>1; i++)
{
if( Union(A[i].priority,A[i].next) )
{
sum+=A[i].weight;
count--;
}
}
if(count==1)
cout<<sum<<endl;
else
cout<<"-1"<<endl;
return 0;
}