题目链接:poj1258 Agri-Net
这题我上个月做过,是个大水题,今天看见有人用prim+heap做的,就学习了下。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #include<vector> 6 #include<set> 7 #define CLR(a,b) memset((a),(b),sizeof((a))) 8 using namespace std; 9 10 const int inf = 0x3f3f3f3f; 11 const int N = 101; 12 int low[N], s[N]; 13 int n, ans, num; 14 struct Edge{ 15 int v,c; 16 Edge(int _v=0,int _c=0):v(_v),c(_c){} 17 bool operator < (const Edge&r)const{ 18 return r.c < c; 19 } 20 }; 21 vector<Edge>g[N]; 22 23 int prim_heap(){ 24 priority_queue<Edge>q; 25 int i, u, v, w; 26 Edge p; 27 ans = 0;//最小生成树总权值 28 num = 0;//已加入最小生成树的顶点数目 29 q.push(Edge(0, 0)); 30 while(!q.empty() && num < n){ 31 p = q.top(); q.pop(); 32 u = p.v; 33 if(s[u]) continue; 34 s[u] = 1; 35 ans += p.c; 36 num++; 37 for(i = 0; i < g[u].size(); ++i){ 38 v = g[u][i].v; 39 if(s[v] == 0){ 40 w = g[u][i].c; 41 if(w < low[v]){ 42 low[v] = w; 43 q.push(Edge(v, w)); 44 } 45 } 46 } 47 } 48 if(num < n) 49 return -1; 50 return ans; 51 } 52 int main(){ 53 int i, j, x; 54 while(scanf("%d", &n) == 1){ 55 for(i = 0; i < n; ++i) 56 g[i].clear(); 57 for(i = 0; i < n; ++i) 58 for(j = 0; j < n; ++j){ 59 scanf("%d", &x); 60 g[i].push_back(Edge(j, x)); 61 } 62 CLR(s, 0); CLR(low, inf); 63 printf("%d ",prim_heap()); 64 } 65 return 0; 66 }