Prim
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = ;
int n, k;
int dis[N], ct[N][N], vis[N]; int Prim()
{
int ans = ;
memset(vis, , sizeof(vis));
/*
for(int i = 1; i <= n; i++)
dis[i] = ct[1][i];
vis[1] = 1;
*/
while()
{
int v = -;
for(int i = ; i <= n; i++)
{
if(!vis[i] && (v == -||dis[v]>dis[i])) v = i;
}
if(v == -) break;
ans += dis[v];
vis[v] = ;
for(int i = ; i <= n; i++)
if(!vis[i])
dis[i] = min(dis[i], ct[v][i]);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
cin >> n >> k;
memset(dis, INF, sizeof(dis));
int tmp;
while(k--)
{
cin >> tmp;
dis[tmp] = ;
}
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
cin >> ct[i][j];
cout << Prim() << endl;
return ;
}
Kruskal
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = ;
struct node
{
int l, r, c;
bool operator < (const node & x)
{
return c < x.c;
}
}A[N*N];
int pre[N];
int Find(int x)
{
if(x == pre[x]) return x;
return pre[x] = Find(pre[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n, m;
cin >> n >> m;
for(int i = ; i <= n; i++)
pre[i] = i;
int t, tmp;
cin >> t;
m--;
while(m--)
{
cin >> tmp;
t = Find(t);
tmp = Find(tmp);
pre[tmp] = t;
}
int cnt = ;
for(int i = ; i <= n; i++)
{
for(int j = ; j <= n; j++)
{
cin >> tmp;
if(i <= j) continue;
A[cnt].l = i, A[cnt].r = j, A[cnt++].c = tmp;
}
}
int ans = ;
sort(A, A+cnt);
for(int i = ; i < cnt; i++)
{
int x =A[i].l, y = A[i].r, ct = A[i].c;
x = Find(x), y = Find(y);
if(x == y) continue;
pre[y] = x;
ans += ct;
}
cout << ans << endl;
return ;
}