最小生成樹(shù)問(wèn)題
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?in("agrinet.in");
ofstream?out("agrinet.out");
int?graph[100][100];
int?n;
int?remain;
int?shortest[100];
bool?visited[100];
void?add(int?node)
{
????visited[node]?=?true;
????for(int?i=0;i<n;++i){
????????if(!visited[i]){
????????????shortest[i]?=?min(shortest[i],graph[node][i]);
????????}
????}
}
int?get_min()
{
????int?res?=?0;
????int?value?=?INT_MAX;
????for(int?i=0;i<n;++i){
????????if(!visited[i]){
????????????if(shortest[i]<value){
????????????????value?=?shortest[i];
????????????????res?=?i;
????????????}
????????}
????}
????return?res;
}
void?solve()
{
????in>>n;
????for(int?i=0;i<n;++i)
????????for(int?j=0;j<n;++j)
????????????in>>graph[i][j];
????memset(visited,0,sizeof(visited));
????for(int?i=0;i<n;++i)
????????shortest[i]?=?INT_MAX;
????int?res?=?0;
????remain?=?n;
????add(0);
????remain--;
????while(remain--){
????????int?t?=?get_min();
????????res+=shortest[t];
????????add(t);
????}
????
????out<<res<<endl;
}
int?main(int?argc,char?*argv[])
{
????solve();?
????return?0;
}