From 4022e5c95210631e4aceb08eaf9d9071aa5aefc4 Mon Sep 17 00:00:00 2001
From: Richard Qin <richard.qin.001@gmail.com>
Date: Tue, 15 Sep 2026 08:16:43 +0800
Subject: Set up a git repo

---
 tests/functional/18_prim.sy | 75 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)
 create mode 100644 tests/functional/18_prim.sy

(limited to 'tests/functional/18_prim.sy')

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();
+}
-- 
cgit v1.2.3