USACO 3.1 Agri-Net (agrinet)
//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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。