最小生成树

wangyichenawm · 2025-04-27 22:08:20 · 个人记录

最小生成树的定义

对于一个有很多顶点和边的图，如果我们能选出一些边，把所有顶点都连起来，形成一个树状的结构（树就是没有环的连通图，就像树枝不会绕成一个圈），而且这些边的权重加起来是最小的，那这个树状结构就是最小生成树。

实现步骤

对所有边排序 从费用最小的边开始选，如果选了这条边不会形成环，就连这条边 一直选边，直到不能再连

例题

P2330 [SCOI2005] 繁忙的都市

经典的最小生成树模板，优先选最值得改造的道路

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5005;
int n, m, cnt;
int fa[N];
struct node{
  int x, y, z;
}a[4 * N];
int get(int x)
{
  if(fa[x] == x) 
    return x;
  return fa[x] = get(fa[x]);
}
void unite(int x, int y)
{
  x = get(x), y = get(y);
  if (x != y)
    fa[x] = y;
  return ;
}
bool cmp(node a,node b)
{
  return a.z < b.z;
}
signed main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    fa[i] = i;
  for (int i = 1; i <= m; i++)
    cin >> a[i].x >> a[i].y >> a[i].z;
  sort(a+1,a+m+1,cmp);
  int ans=0,sum=0;
  for(int i=1;i<=m;i++)
  {
    int f1=get(a[i].x),f2=get(a[i].y);
    if(f1!=f2)
    {
      unite(f1, f2);
      ans=a[i].z;
      sum++;
    }
  }
  cout<<sum<<' '<<ans;
  return 0;
}

P2121 拆地毯

“地毯的美丽度之和最大”，所以...

最小生成树——启动！！！

include<bits/stdc++.h>

define int long long

using namespace std; const int N = 1e5 + 5; struct node{ int x, y, z; }a[N]; int n, m, k; int fa[4*N]; int get(int x) { if(fa[x] == x) return x; return fa[x] = get(fa[x]); } void unite(int x, int y) { x = get(x), y = get(y); if (x != y) fa[x] = y; return ; } bool cmp(node x, node y) { return x.z > y.z; } signed main() { cin >> n >> m >> k; for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y >> a[i].z; sort(a + 1, a + m + 1, cmp); int ans = 0, sum = 0; for(int i = 1; i <= m; i++) { int f1 = get(a[i].x), f2 = get(a[i].y); if(f1 != f2) { unite(f1, f2); ans += a[i].z; sum++; if(sum == k) { cout << ans; return 0; } } } return 0; }