hihoCoder#1109 最小生成樹三·堆優化的Prim算法

原題位址

坑了我好久。。。送出總是WA，找了個AC代碼，然後做同步随機資料diff測試，結果發現資料量小的時候，測試幾十萬組随機資料都沒問題，但是資料量大了以後就會不同，思前想後就是不知道算法寫得有什麼問題，因為本來就沒什麼複雜的地方嘛！

後來，突然靈機一動，莫非又是數組開小了？

突然意識到，我是用數組儲存圖的，是以對于無向圖，邊數實際上是輸入的2倍，于是把數組開成2倍大小，AC了。。。。

我總算知道之前這句溫馨提示的意思了。。。

代碼：

1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 
 5 using namespace std;
 6 
 7 #define MAX_POINT 2000008
 8 
 9 int N, M;
10 int u[MAX_POINT];
11 int v[MAX_POINT];
12 int w[MAX_POINT];
13 
14 struct mycmp {
15   bool operator()(const int &i, const int &j) const {
16     return w[i] > w[j];
17   }
18 };
19 
20 int f[MAX_POINT];
21 int n[MAX_POINT];
22 priority_queue<int, vector<int>, mycmp> q;
23 bool visited[MAX_POINT];
24 
25 int prime() {
26   int res = 0;
27   int left = N - 1;
28 
29   visited[1] = true;
30   for (int i = f[1]; i != 0; i = n[i])
31     q.push(i);
32 
33   while (!q.empty() && left) {
34     int e = q.top();
35     q.pop();
36     if (visited[v[e]])
37       continue;
38     res += w[e];
39     left--;
40     visited[v[e]] = true;
41     for (int i = f[v[e]]; i != 0; i = n[i]) {
42       if (!visited[v[i]])
43         q.push(i);
44     }
45   }
46 
47   return res;
48 }
49 
50 int main() {
51   memset(f, 0, sizeof(f));
52   memset(visited, 0, sizeof(visited));
53   scanf("%d%d", &N, &M);
54   for (int i = 1, j = 1; i <= M; i++) {
55     int a, b, c;
56     scanf("%d%d%d", &a, &b, &c);
57     u[j] = a;
58     v[j] = b;
59     w[j] = c;
60     n[j] = f[a];
61     f[a] = j++;
62     u[j] = b;
63     v[j] = a;
64     w[j] = c;
65     n[j] = f[b];
66     f[b] = j++;
67   }
68 
69   printf("%d\n", prime());
70 
71   return 0;
72 }      

轉載于:https://www.cnblogs.com/boring09/p/4397204.html