首页 > 代码库 > USACO agrinet Prim
USACO agrinet Prim
裸最短生成树
/* ID:kevin_s1 PROG:agrinet LANG:C++ */ #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <map> #include <set> #include <algorithm> #include <cstdlib> #include <list> #include <cmath> using namespace std; #define MAXN 110 #define INF 100001 //gobal variable==== int N; int Edge[MAXN][MAXN]; int lowcost[MAXN]; int sumdist; //================== //function========== void prim(){ lowcost[1] = -1; int v; for(int i = 2; i <= N; i++){ lowcost[i] = Edge[1][i]; } for(int i = 2; i <= N; i++){ int min = INF; for(int k = 2; k <= N; k++){ if(lowcost[k] != -1 && lowcost[k] < min){ v = k; min = lowcost[k]; } } sumdist += min; lowcost[v] = -1; for(int k = 1; k <= N; k++){ if(lowcost[k] > Edge[v][k]) lowcost[k] = Edge[v][k]; } } } //================== int main(){ freopen("agrinet.in","r",stdin); freopen("agrinet.out","w",stdout); cin>>N; for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ cin>>Edge[i][j]; } } memset(lowcost, 0, sizeof(lowcost)); sumdist = 0; prim(); cout<<sumdist<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。