首页 > 代码库 > poj 1258 Agri-Net 解题报告

poj 1258 Agri-Net 解题报告

2024-07-17 20:37:23   215人阅读

题目链接：http://poj.org/problem?id=1258

题目意思：给出 n 个 farm，每个farm 之间通过一定数量的fiber 相连，问使得所有farm 直接或间接连通的 最少 fiber 数是多少。

     赤裸裸的最小生成树，用prim做的。

     有个地方写错，wa 了 几次。

    

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4  5 const int farm_num = 10000 + 10; 6 const int INF = 1e9; 7 int farm[farm_num][farm_num]; 8 int dist[farm_num], vis[farm_num]; 9 int ans, N;10 11 void prim()12 {13     int k;14     for (int i = 1; i <= N; i++)15     {16         vis[i] = 0;17         dist[i] = INF;18     }19     // 假设从编号为 1 的farm 出发20     dist[1] = 0, ans = 0;21     for (int i = 1; i <= N; i++)22     {23         int tmp = INF;24         for (int j = 1; j <= N; j++)25         {26             if (!vis[j] && dist[j] < tmp)27             {28                 tmp = dist[j];29                 k = j;30             }31         }32         vis[k] = 1;33         ans += tmp;34         for (int j = 1; j <= N; j++)35         {36             if (!vis[j] && dist[j] > farm[k][j])  // 一开始将dist[j] > farm[k][j]直接写成farm[k][j]了= =37                 dist[j] = farm[k][j];38         }39     }40 }41 42 int main()43 {44     while (scanf("%d", &N) != EOF)45     {46         for (int i = 1; i <= N; i++)47         {48             for (int j = 1; j <= N; j++)49                 scanf("%d", &farm[i][j]);50         }51         prim();52         printf("%d\n", ans);53     }54     return 0;55 }

 

    


联系
我们