本文共 1812 字，大约阅读时间需要 6 分钟。

为了解决连接所有农场并用最少光纤的问题，我们可以使用Kruskal算法来构建最小生成树。这是一个经典的图论问题，适合使用并查集（Union-Find）来高效解决。

方法思路

我们将每个农场看作图中的一个节点，农场之间的距离作为边的权重。目标是找到连接所有节点的最小总权重的树。

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          using namespace std; #define N_MAX 100 #define INF 100005 struct Node { int u, v, l; }; int parent[N_MAX]; int rank[N_MAX]; bool cmp(Node a, Node b) { return a.l < b.l; } void main() { freopen("D:\\input.txt", "r", stdin); int n; while (scanf("%d", &n) != EOF) { int edges[N_MAX][N_MAX]; for (int i = 0; i < n; ++i) { int len = 0; do { char c; istringstream iss; iss >> c; if (c == ' ') continue; iss >> edges[i][len]; len++; } while (len < n); } int m = 0; int sum = 0; for (int i = 0; i < n; ++i) { parent[i] = i; rank[i] = 1; } vector
         
           p; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (edges[i][j] != 0) { p.push_back({i, j, edges[i][j]}); } } } sort(p.begin(), p.end(), cmp); int components = n; int res = 0; while (components > 1 && !p.empty()) { Node edge = p.front(); p.pop_front(); int u = edge.u; int v = edge.v; int root_u = find(u); int root_v = find(v); if (root_u != root_v) { sum += edge.l; if (rank[root_u] > rank[root_v]) { parent[root_v] = root_u; } else { parent[root_u] = root_v; if (rank[root_u] == rank[root_v]) { rank[root_v]++; } } components--; } } if (components == 1) { cout << sum << endl; } else { cout << -1 << endl; } } }
         
        
       
      
     
    
   

代码解释

这种方法确保了在最少的光纤中连接所有农场，满足了问题的需求。

转载地址：http://buxfk.baihongyu.com/