maxn=100；
var
cost:array[1..maxn,1..maxn] of longint；
mincost,closed:array[1..maxn] of longint；
min,tot,k,i,j,n,x,y:longint；
begin
readln(n)；
for i:=1 to n do
for j:=1 to n do
begin
read(cost[i,j])；
if (i<>j) and (cost[i,j]=0) then cost[i,j]:=maxlongint；
end；
for i:=1 to n do
begin
mincost[i]:=cost[1,i]；
closed[i]:=1；
end；
for i:=2 to n do
begin
min:=maxlongint；
for j:=1 to n do
if (mincost[j]<min) and (mincost[j]<>0) then
begin
min:=mincost[j]；
k:=j；
end；
inc(tot,mincost[k])；
mincost[k]:=0；
for j:=1 to n do
if (mincost[j]>cost[k,j]) and (mincost[j]<>0) then
begin
mincost[j]:=cost[k,j]；
closed[j]:=k；
end；
end；
writeln(tot)；
end.
Show Problem 题目:拜年
问题编号:142 My Flag:Unaccepted
题目类型 图结构
描述
题目描述:
拜年是中国人少不了的风俗.还没过年呢,刚上小学的妮妮已经等不及要给她的小伙伴去拜年了,但是她不知道如
何规划才会使自己走的路最少.所以请叫您咯,她不想落下任何一位伙伴.为了走少花精力,她想走最少的路程去所
有伙伴的家里.您将得到一份各伙伴家路程的列表,您必须找出能走最少路程去所有小伙伴家的最少路程.
输入格式
输入文件第一行为妮妮小伙伴的个数,n(3<=n<=100)
下面是一个n*n的矩阵,表示每个小伙伴家的距离d(d<=100000),可以保证所有小伙伴都相互认识.
输出格式
只有一个输出为要去所有小伙伴家要走的最少路程
样例输入
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
样例输出
28
*/
//#include<fstream>
#include<iostream>
#include<climits>
using namespace std；
//ofstream fout ("pid193.out")；
bool mst[1000][1000]={false},visited[1000]={false}；
int n,G[1000][1000]；
int prim(){
int count=0；
visited[0]=true；
for (int i=0；i<n-1；i++){
int min=INT_MAX,minj,mink；
for (int j=0；j<n；j++)
if (visited[j])
for (int k=0；k<n；k++)
if (!mst[j][k]/*&&!mst[k][j]*/&&!visited[k]&&min>G[j][k]){
minj=j；
mink=k；
min=G[j][k]；
}
visited[mink]=mst[minj][mink]/*=mst[mink][minj]*/=true；
count+=G[minj][mink]；
}
return count；
}
int main (void){
cin>>n；
for (int i=0；i<n；i++)
for (int j=0；j<n；j++)
cin>>G[i][j]；
cout<<prim()；
// int count=0；
// for (int i=0；i<n-1；i++)
// for (int j=i+1；j<n；j++)
// if (mst[i][j]) count+=G[i][j]；
// cout<<count；
// while(1)；
return 0；
}
var
f:array[1..100,1..100]of longint；
m,n,o,p,q,r:longint；
procedure prim；
var
lowcost,closest:array[1..100]of longint；
i,j,k,min:longint；
begin
for i:=1to m do
begin
lowcost[i]:=f[1,i]；
closest[i]:=1；
end；
for i:=1to m-1do
begin
min:=2147483647；
for j:=1to m do
if(lowcost[j]<min)and(lowcost[j]<>-2147483647)
then begin
min:=lowcost[j]；
k:=j；
end；
lowcost[k]:=-2147483647；
for j:=1to m do
if f[k,j]<lowcost[j]
then begin
lowcost[j]:=f[k,j]；
closest[j]:=k；
end；
end；
j:=0；
for i:=2to m do
j:=j+f[closest[i],i]；
write(j)；
end；
function mi(i,j:longint):longint；
begin
if i<j
then mi:=i
else mi:=j；
end；
begin
readln(m)；
for o:=1to m do
begin
for p:=1to m do
read(f[o,p])；
readln；
end；
prim；
end.