//Main idea
//Minimun Spannig Tree, we use Kruskal‘s algorithm;

/*
ID: haolink1
PROG: agrinet
LANG: C++
*/

//#include <iostream>
#include <fstream>
#include <list>
using namespace std;

class Edge{
public:
    int x_;
    int y_;
    int dist_;
    Edge(int x,int y, int dist):
        x_(x),y_(y),dist_(dist){}
};

list<Edge> nodes;
short set_num[100];
int N = 0;

bool CompareDist(Edge e1,Edge e2){
    if(e1.dist_ <= e2.dist_ )
        return 1;
    else return 0;
}

void Union(short x_set,short y_set){
    short min_set = x_set < y_set ? x_set : y_set;
    short max_set = x_set > y_set ? x_set : y_set;
    for(int i = 0; i < N; i++){
        if(set_num[i] == max_set){
            set_num[i] = min_set;
        }
    }
}


int MST_Kruskal(){
    int total_cost = 0;
    for(int i = 0; i < N; i++){
        set_num[i] = i;
    }
    nodes.sort(CompareDist);
//    for(list<Edge>::iterator it = nodes.begin(); it != nodes.end(); it++){
//        cout<<it->x_<<" "<<it->y_<<" "<<it->dist_<<endl;
//    }
    for(list<Edge>::iterator it = nodes.begin(); it != nodes.end(); it++){
        if(set_num[it->x_] != set_num[it->y_]){
            total_cost += it->dist_;
            Union(set_num[it->x_],set_num[it->y_]); 
        } 
    }
    return total_cost;
}

int main(){
    ifstream fin("agrinet.in");
    fin >> N;
    int value = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            fin >> value;
            if(j > i){
                nodes.push_back(Edge(i,j,value));            
            }
        }
    }
    ofstream fout("agrinet.out");
    fout<<MST_Kruskal()<<endl;
    return 0;
}

//Main idea
//Minimun Spannig Tree, we use Prim‘s algorithm;

/*
ID: haolink1
PROG: agrinet
LANG: C++
*/

#include <iostream>
#include <fstream>
using namespace std;

const int INF = 100001;
int N = 0;
bool is_visited[100];
int node_key[100];
int dist[100][100];
//parent[i] denotes i‘s parent node;
//Start from node 0, so the parent[i]‘s initial value can be 0;    
int parent[100];

int ExtractMin(){
    int index = -1;
    int min = INF;
    for(int i = 0; i < N; i++){
        if(node_key[i] < min && is_visited[i] == 0){
            min = node_key[i];
            index = i;
        } 
    }
    //Note if you set index > 0, there will be a endless loop;
    if(index >= 0)
        is_visited[index] = 1;
    return index;
}

int MST_Prim(){
    for(int i = 0; i < N; i++){
        node_key[i] = INF;
    }
    node_key[0] = 0; 
    int total_cost = 0;
    while(1){
        int i = ExtractMin();
        if(i < 0)
            break;
        if(parent[i] != i)
            total_cost += dist[parent[i]][i];
        for(int j = 0; j < N; j++){
            if(i != j && dist[i][j] < node_key[j]){
                node_key[j] = dist[i][j];
                //Note record j‘s parent to calculate the distance;
                //Start from node 0, so the parent[i]‘s initial value can be 0;    
                parent[j] = i;             
            }

        }
    }
    return total_cost;
}

int main(){
    ifstream fin("agrinet.in");
    fin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            fin >> dist[i][j];
        }
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cout<<dist[i][j]<<" ";
        }
        cout<<endl;
    } 
    ofstream fout("agrinet.out");
    cout<<MST_Prim()<<endl;
    return 0;
}

USACO 3.1 Agri-Net (agrinet),布布扣,bubuko.com

USACO 3.1 Agri-Net (agrinet)