poj 1258 AgriNet

　　还是简单MST，拿来测试模板的性能...
View Code
  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 const int MAXV = 105, MAXE = 105 * 105, INF = (~0u)>>2;
  7 struct edge{
  8     int t, w, next;
  9 }es[MAXE << 1];
 10 int h[MAXV], cnt, n, heap[MAXV << 1], size, pos[MAXV], dist[MAXV];
 11 
 12 void init(){
 13     cnt = size = 0;
 14     memset(h, 0, sizeof(h));
 15     memset(heap, 0, sizeof(heap));
 16     memset(pos, 0, sizeof(pos));
 17     memset(dist, 0, sizeof(dist));
 18 }
 19 
 20 void addedge(int x, int y, int z){
 21     es[++cnt].t = y;
 22     es[cnt].next = h[x];
 23     es[cnt].w = z;
 24     h[x] = cnt;
 25 }
 26 
 27 void heapup(int k){
 28     while(k > 1){
 29         if(dist[heap[k >> 1]] > dist[heap[k]]){
 30             swap(pos[heap[k >> 1]], pos[heap[k]]);
 31             swap(heap[k >> 1], heap[k]);
 32             k >>= 1;
 33         }
 34         else break;
 35     }
 36 }
 37 void heapdown(int k){
 38     while((k << 1) <= size){
 39         int j;
 40         if((k << 1) == size || dist[heap[k << 1]] < dist[heap[k << 1 | 1]])
 41             j = k << 1;
 42         else
 43             j = k << 1 | 1;
 44         if(dist[heap[k]] > dist[heap[j]]){
 45             swap(pos[heap[k]], pos[heap[j]]);
 46             swap(heap[k], heap[j]);
 47             k = j;
 48         }
 49         else break;
 50     }
 51 }
 52 void push(int v, int d){
 53     dist[v] = d;
 54     heap[++size] = v;
 55     pos[v] = size;
 56     heapup(size);
 57 }
 58 
 59 int pop(){
 60     int ret = heap[1];
 61     swap(pos[heap[size]], pos[heap[1]]);
 62     swap(heap[size], heap[1]);
 63     size--;
 64     heapdown(1);
 65     return ret;
 66 }
 67 
 68 int prim(){
 69     int mst = 0, i, p;
 70 
 71     push(1, 0);
 72     for(i = 2; i <= n; i++)
 73         push(i, INF);
 74     for(i = 1; i <= n; i++){
 75         int t = pop();
 76         mst += dist[t];
 77         pos[t] = -1;
 78         for(p = h[t]; p; p = es[p].next){
 79             int dst = es[p].t;
 80             if(pos[dst] != -1 && dist[dst] > es[p].w){
 81                 dist[dst] = es[p].w;
 82                 heapup(pos[dst]);
 83                 heapdown(pos[dst]);
 84             }
 85         }
 86     }
 87     return mst;
 88 }
 89 
 90 void deal(){
 91     int c;
 92 
 93     for (int i = 1; i <= n; i++){
 94         for (int j = 1; j <= n; j++){
 95             scanf("%d", &c);
 96             if (i != j){
 97                 addedge(i, j, c);
 98             }
 99         }
100     }
101     printf("%d\n", prim());
102 }
103 
104 int main(){
105 #ifndef ONLINE_JUDGE
106     freopen("in", "r", stdin);
107 #endif
108     while (~scanf("%d", &n)){
109         init();
110         deal();
111     }
112 
113     return 0;
114 }
——written by Lyon