?? 1233.txt
字號:
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
struct Node
{
int adjvex;
int cost;
};
const int Max=101;
Node road[Max][Max];
int prim[Max];
bool v[Max];
int MST_Prim(int n)
{
int i,j,k,now,lowcost,min;
now=1;lowcost=0;v[1]=true;
for(i=road[1][0].adjvex;i>0;i--)
prim[ road[1][i].adjvex ]=road[1][i].cost;
for(i=1;i<n;i++)
{
for(j=1,min=prim[0];j<Max;j++)
if(min>prim[j])
{ min=prim[j];now=j;}
lowcost+=min;
prim[now]=9999;
v[now]=true;
for(j=road[now][0].adjvex;j>0;j--)
if(!v[road[now][j].adjvex] && prim[ road[now][j].adjvex ] > road[now][j].cost)
prim[ road[now][j].adjvex ]=road[now][j].cost;
}
return lowcost;
}
int main()
{
int t,n,i,x,y,s;
while(scanf("%d",&n)==1 && n!=0)
{
memset(road,0,sizeof(road));
for(i=0;i<Max;i++)
{ prim[i]=9999;v[i]=false;}
t=n*(n-1)/2;
for(i=0;i<t;i++)
{
scanf("%d %d %d",&x,&y,&s);
road[x][0].adjvex++;
road[x][ road[x][0].adjvex ].adjvex=y;
road[x][ road[x][0].adjvex ].cost=s;
road[y][0].adjvex++;
road[y][ road[y][0].adjvex ].adjvex=x;
road[y][ road[y][0].adjvex ].cost=s;
}
cout<<MST_Prim(n)<<endl;
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -