大意：新镇长竞选宣言就是将网络带到每一个农场，给出农场个数，两两之间建光缆的耗费，求所有都联通的最小耗费。

 

思路：最小生成树，因为边比较稠密，用Prim做。

 

PS；对于比较稠密的图，用Prim，对于比较稀疏的图，用 Kruskal。Kruskal是找边的过程，稀疏的话会比较快。

 

1 #include 
      
        2 #include 
       
         3 #define INF 0x3f3f3f3f 4  5 int dis[110]; 6 int Map[110][110]; 7 int n; 8 int Ans; 9 10 int min(int a, int b)11 {12     return a > b ? b : a;13 }14 15 void  Prim()16 {17     int Min_ele, Min_node;18     memset(dis, INF, sizeof(dis));19     Ans = 0;20     int r = 1;21     for(int i = 1; i < n; i++)22     {23         dis[r] = -1;24         Min_ele = INF;25         for(int j = 1; j <= n; j++)26         {27             if(dis[j] >= 0)28             {29                 dis[j] = min(dis[j], Map[r][j]);30                 if(dis[j] < Min_ele)31                 {32                     Min_ele = dis[j];33                     Min_node = j;34                 }35             }36         }37         r = Min_node;38         Ans += Min_ele;39     }40 }41 42 43 void Solve()44 {45     while(~scanf("%d", &n))46     {47         memset(Map, 0, sizeof(Map));48         for(int i = 1; i <= n; i++)49         {50             for(int j = 1; j <= n; j++)51             {52                 scanf("%d", &Map[i][j]);53             }54         }55         Prim();56         printf("%d\n", Ans);57     }58 }59 60 int main()61 {62     Solve();63 64     return 0;65 }