Poj 1258 Agri-Net

浏览数：67 / 时间：2015年06月09日

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

题意：给N个点，和N*N的矩阵（表示Ni到Nj的距离），求连通所有点的最小距离。

题解：最小生成树模板……prim……

每两个点之间距离不超过100，000，刚看时INF打成了10，010……Holy shit……怒WA……

 1 //
 2 //  main.cpp
 3 //  POJ 1258
 4 //
 5 //  Created by zhang on 14-3-31.
 6 //  Copyright (c) 2014年 apple. All rights reserved.
 7 //
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <algorithm>
12 
13 using namespace std;
14 
15 const int maxn=110;
16 const int INF=1001000;
17 int cost[maxn][maxn];
18 int MINC[maxn];
19 bool used[maxn];
20 int V;
21 
22 int prim()
23 {
24     for (int i=0; i<V; i++) {
25         MINC[i]=INF;
26         used[i]=false;
27     }
28     MINC[0]=0;
29     int res=0;
30     while (1) {
31         int v=-1;
32         for (int u=0; u<V; u++) {
33             if (!used[u]&&(v==-1||MINC[u]<MINC[v])) {
34                 v=u;
35             }
36         }
37         if (v==-1) {
38             break;
39         }
40         used[v]=true;
41         res+=MINC[v];
42         for (int u=0; u<V; u++) {
43             MINC[u]=min(MINC[u],cost[v][u]);
44         }
45     }
46     return res;
47 }
48 int main()
49 {
50     //freopen("/Users/apple/Desktop/POJ 1258/POJ 1258/in", "r", stdin);
51     //freopen("/Users/apple /Desktop/POJ 1258/POJ 1258/out", "w", stdout);
52     int N;
53     while (scanf("%d",&N)!=EOF) {
54         V=N;
55         for (int i=0; i<N; i++) {
56             for (int j=0; j<N; j++) {
57                 cin>>cost[i][j];
58                 //scanf("%d",&cost[i][j]);
59             }
60         }
61         printf("%d\n",prim());
62     }
63     return 0;
64 }