最小生成树问题
#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;
}