diff options
| author | Richard Qin <richard.qin.001@gmail.com> | 2026-09-15 08:16:43 +0800 |
|---|---|---|
| committer | Richard Qin <richard.qin.001@gmail.com> | 2026-09-15 08:16:43 +0800 |
| commit | 4022e5c95210631e4aceb08eaf9d9071aa5aefc4 (patch) | |
| tree | a5922559836e45fb3459a3d070367912e1035b1a /tests/functional/18_prim.sy | |
| download | rcc-4022e5c95210631e4aceb08eaf9d9071aa5aefc4.tar.gz rcc-4022e5c95210631e4aceb08eaf9d9071aa5aefc4.tar.xz | |
Diffstat (limited to 'tests/functional/18_prim.sy')
| -rw-r--r-- | tests/functional/18_prim.sy | 75 |
1 files changed, 75 insertions, 0 deletions
diff --git a/tests/functional/18_prim.sy b/tests/functional/18_prim.sy new file mode 100644 index 0000000..9a6d246 --- /dev/null +++ b/tests/functional/18_prim.sy @@ -0,0 +1,75 @@ +int quick_read(){
+ int ch = getch(); int x = 0, f = 0;
+ while (ch < 48 || ch > 57){
+ if (ch == 45) f = 1;
+ ch = getch();
+ }
+ while (ch >= 48 && ch <=57){
+ x = x * 10 + ch - 48;
+ ch = getch();
+ }
+ if (f) return -x;
+ else return x;
+}
+const int maxm = 1005;
+const int maxn = 105;
+int n, m;
+int u[maxm], v[maxm], c[maxm], fa[maxm];
+int find(int x){
+ if (x == fa[x]) return x;
+ int asdf = find(fa[x]);
+ fa[x] = asdf;
+ return asdf;
+}
+int same(int x, int y){
+ x = find(x);
+ y = find(y);
+ if (x == y) return 1;
+ return 0;
+}
+int prim(){
+ int i = 0;
+ while (i < m){
+ int j = i + 1;
+ while (j < m){
+ if (c[i] > c[j]){
+ int t = u[i];
+ u[i] = u[j];
+ u[j] = t;
+ t = v[i];
+ v[i] = v[j];
+ v[j] = t;
+ t = c[i];
+ c[i] = c[j];
+ c[j] = t;
+ }
+ j = j + 1;
+ }
+ i = i + 1;
+ }
+ i = 1;
+ while (i <= n){
+ fa[i] = i;
+ i = i + 1;
+ }
+ i = 0;
+ int res = 0;
+ while (i < m){
+ if (same(u[i], v[i])) continue;
+ res = res + c[i];
+ fa[find(u[i])]=v[i];
+ i = i + 1;
+ }
+ return res;
+}
+int main(){
+ int n = quick_read(), m = quick_read();
+ int i = 0;
+ while (i < m){
+ u[i] = quick_read();
+ v[i] = quick_read();
+ c[i] = quick_read();
+ i = i + 1;
+ }
+ return prim();
+}
|