#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void prim( vector <vector <int> > &cost , int N);
int main ()
{
vector <vector <int> > cost;
vector <int> temp;
int N;
int x;
cin >> N;
for ( int i = 0; i < N; i ++ ) {
for ( int j = 0; j < N; j ++ ) {
cin >> x;
if ( x == -1 ) {
x = INT_MAX;
}
temp.push_back(x);
}
cost.push_back(temp);
temp.clear();
}
prim(cost, N);
cin.get();
cin >> N;
return 0;
}
void prim( vector <vector <int> > &cost , int N)
{
vector <int> near(N);
vector <vector<int> > T;
int mincost;
int first = 0;
int second = 0;
mincost = INT_MAX;
for ( int i = 0; i < N; i ++ ) {
for ( int j = 0; j < N; j ++ ) {
if ( cost[i][j] < mincost ) {
mincost = cost[i][j];
first = i;
second = j;
}
}
}
//near[first] = near[second] = -1;
vector <int> temp;
temp.push_back(first);
temp.push_back(second);
T.push_back(temp);
temp.clear();
for ( int i = 0; i < N; i ++ ) {
if ( cost[i][first] < cost[i][second] ) {
near[i] = first;
} else {
near[i] = second;
}
}
near[first] = near[second] = -1;
for ( int i = 1; i < N - 1; i++ ) {
int min;
min = INT_MAX;
int minindex = -1;
for ( int j = 0; j < N; j ++ ) {
if ( (near[j] != -1) && cost[j][near[j]] < min ) {
min = cost[j][near[j]];
minindex = j;
}
}
if ( minindex == -1 ) {
cout << mincost << endl;
return;
}
temp.push_back(minindex);
temp.push_back(near[minindex]);
T.push_back(temp);
temp.clear();
mincost += min;
near[minindex] = -1;
for ( int k = 0; k < N; k ++ ) {
if ( (near[k]!= -1) && (cost[k][minindex] <
cost[k][near[k]] ) ) {
near[k] = minindex;
}
}
}
cout << endl << mincost << endl;
cin.get();
}
/*Input
7
-1 28 -1 -1 -1 10 -1
28 -1 16 -1 -1 -1 17
-1 16 -1 12 -1 -1 -1
-1 -1 12 -1 22 -1 18
-1 -1 -1 22 -1 25 24
10 -1 -1 -1 25 -1 -1
-1 17 -1 18 24 -1 -1
*/
Happy coding!!!
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
