USACO 3.1 Agri

//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){}
};

listEdge 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(listEdge::iterator it = nodes.begin(); it != nodes.end(); it++){
//        coutit-x_" "it-y_" "it-dist_endl;
//    }
    for(listEdge::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");
    foutMST_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++){
            coutdist[i][j]" ";
        }
        coutendl;
    } 
    ofstream fout("agrinet.out");
    coutMST_Prim()endl;
    return 0;
}



最新回复(0)
/jishuXXn8dJitB87Pik_2FxgF_2FOH9coHQSis_2FcyoS7zp91QYzQ_3D4858451
8 简首页