http://poj.org/problem?id=1258

裸求最小生成树

这句话好像没什么影响"Physically, they are limited in length to 80 characters, so some lines continue onto others"

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define READ() freopen("in.txt", "r", stdin); 6 #define MAXV 20007 7 #define INF 0x3f3f3f3f 8 using namespace std; 9 10 typedef pair
         
           P;11 int N;12 struct Edge13 {14     int to, cost, next;15     Edge () {}16     Edge(int to, int cost, int next) : to(to), cost(cost), next(next) {}17 }edge[MAXV];18 19 int head[MAXV];20 int num = 0;21 22 void Add(int from, int to, int cost)23 {24     edge[num] = Edge(to, cost, head[from]);25     head[from] = num++;26 }27 28 int prim()29 {30     int res = 0;31     int dist[MAXV];32     bool use[MAXV];33     priority_queue
          
           , greater
           
 > que;34 fill(dist, dist+MAXV, INF);35 fill(use, use+MAXV, false);36 dist[1] = 0;37 que.push(P(dist[1], 1));38 while (!que.empty())39 {40 P p = que.top();41 que.pop();42 int v = p.second, d = p.first;43 if (!use[v])//**44 {45 res += dist[v];46 }47 use[v]= true;48 if (dist[v] < d) continue;49 int t = head[v];50 while (t != -1)51 {52 Edge e = edge[t];53 if (!use[e.to] && dist[e.to] > e.cost)//**54 {55 dist[e.to] = e.cost;56 que.push(P(dist[e.to], e.to));57 }58 t = e.next;59 }60 }61 return res;62 }63 64 65 int main()66 {67 READ()68 while(~scanf("%d", &N))69 {70 int cost;71 num = 0;72 memset(head, -1, sizeof(head));73 memset(edge, -1, sizeof(edge));74 for (int i = 1; i <= N ;i ++)75 {76 for (int j = 1; j <= N; j++)77 {78 scanf("%d", &cost);79 if (i == j) continue;80 Add(i, j, cost);81 Add(j, i, cost);82 }83 }84 int ans = prim();85 cout << ans << endl;86 }87 88 }