最小生成树

一、最小生成树定义

最小生成树定义：在一张带权无向图中，最小生成树是一棵生成树，它的边权值之和最小。

什么是生成树？

生成树是一棵包含原图所有顶点的树，它的边的集合是原图的一个子集，并且任意两点之间有且只有一条简单路径。

二、常见求最小生成树的两种算法

1.Kruscal算法

算法的主要思想是：按照边权的大小依次选边，如果这条边的两个端点没在一个连通块里面，那就把这条边加到最小生成树的边集里面。

具体步骤：

边按照权值排序
按照顺序依次加边
重复以上操作直到有最小生成树边集里面有条边为止。

复杂度：,其中为边数。

注意：存边是存的单向边，适用于稀疏图。

P3366 【模板】最小生成树

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50100,M = 2e5+10;

struct Node
{
	int x,y,v;
	bool operator <(const Node &A)const{
		return v<A.v;
	}
}a[M+1];

int n,m,fa[N+1];

int find(int x)
{
	if(x==fa[x])return x;
	return fa[x] = find(fa[x]);
}

int kruskal()
{
	for(int i = 1;i<=n;i++)fa[i] = i;
	sort(a+1,a+1+m);
	int ans = 0,cnt = n;
	for(int i = 1;i<=m;i++)
	{
		int x = find(a[i].x),y = find(a[i].y);
		if(x!=y)
		{
			fa[x] = y;
			ans += a[i].v;
			--cnt;
		}
		if(cnt==1)break;
	}
	if(cnt!=1)return -1;
	return ans;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].v;
	}
	int ans = kruskal();
	if(ans==-1)cout<<"orz\n";
	else cout<<ans<<endl;
	return 0;
}

2.Prim()算法

算法是主要思想是：从任意一个顶点开始，每次选择一个与当前连通块相邻的权值最小的边，并把它加到最小生成树的边集里面，直到所有顶点都加入。

具体步骤：

随机选择一个顶点作为起点
将于起点相邻的边按照边权从小到大排序，并选择权值最小的边加入到最小生成树的边集里面。
将新加入的点加入到连通块中，并将于它相邻的边按照边权从小到大排序。
重复2，3步骤直到所有点是加入。

时间复杂度：,其中为顶点数。若用堆优化时间复杂度

注意：存的是双向边,适合稠密图。

朴素写法：

完整写法，不一定是连通图情况

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int y,v;
	Node(int _y,int _v){y = _y;v = _v;};
};
std::vector<Node>edge[N+1];
int n,m,dist[N+1];
bool b[N+1];

int Prim()
{
	memset(b,false,sizeof(b));
	memst(dist,127,sizeof(dist));
	dist[1] = 0;
	int ans = 0,tot = 0;
	while(1)
	{
		int x = -1;
		for(int i = 1;i<=n;i++)
		{
			if(!b[i]&&dist[i]<(1<<30))
			{
				if(x==-1||dist[i]<dist[x])
					x=i;
			}
		}
		if(x==-1)break;//找不到符合条件的能加入c中的了
		++tot;
		ans += dist[x];
		b[x]=true;
		for(auto i:edge[x])
		{
			dist[i.y] = min(dist[i.y],i.v);//dist记录的是当前这个点到c中的边权最小值
		}
	}
		if(tot == n)return ans;
		else return -1;//不连通
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	return 0;
}

堆优化写法

和的区别
差别只在于最后循环体内的松弛操作。

最小生成树只关心所有边的和最小，所以有，即每个点直连其他点的最小值（最多只有两个节点之间的权值和）
最短路径树只搜索权值最小，所以有，即每个点到其他点的最小值（最少是两个节之间的权值和）

#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int y,v;
	Node(int _y,int _v){y = _y;v = _v;};
};
const int N = 50000;
int n,m,dist[N+1];
std::vector<Node> edge[N+1];
bool b[N+1];
set<pair<int,int>>q;

void Prim()
{
	memset(b,false,sizeof(b));
	memset(dist,127,sizeof(dist));
	dist[1] = 0;
	q.clear();
	for(int i = 1;i<=n;i++)
	{
		q.insert({dist[i],i});
	}
	int ans = 0;
	while(!q.empty())
	{
		int x= q.begin()->second;
		q.erase(q.begin());
		ans += dist[x];
		b[x]=true;
		for(auto i:edge[x])
		{
			if(!b[i.y]&&i.v<dist[i.y])
			{
				q.erase({dist[i.y],i.y});
				dist[i.y]=i.v;
				q.insert({dist[i.y],i.y});
			}
		}
	}
	cout<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i= 1;i<=m;i++)
	{
		int x,y,v;
		cin>>x>>y>>v;
		edge[x].push_back({y,v});
		edge[y].push_back({x,v});
	}
	Prim();
	return 0;
}

三、最小生成树常见应用

（1）对于Kruscal原理的理解：

例题1：P1396 营救

题意：给你起点和终点，问你在通往到的路径上最大拥挤度最小是多少？

思路：因为我们知道用建立最小生成树的时候是从小往大加边的，那么第一次加入且使得和连通的边就是答案了。

#include<bits/stdc++.h>
using namespace std;
const int N = 10000,M = 20000;
struct Node
{
	int x,y,v;
	bool operator <(const Node &A)const{
		return v<A.v;
	}
}a[M+1];//存边

int n,m,s,t,fa[N+1];
int findset(int i)
{
	if(i==fa[i])return i;
	return fa[i]=findset(fa[i]);
}

void Kruskal()
{
	for(int i =1 ;i<=n;i++)
	{
		fa[i] =i;
	}
	sort(a+1,a+1+m);
	for(int i = 1;i<=m;i++){
		int x= findset(a[i].x),y = findset(a[i].y);
		if(x!=y)
		{
			fa[x] = y;
		}
		if(findset(s)==findset(t)){
			cout<<a[i].v<<endl;
			return;
		}
	}
}

int main()
{
	cin>>n>>m>>s>>t;
	for(int i = 1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].v;
	}
	Kruskal();
	return 0;
}

当然了，这道题的解法还有很多。求最大值最小，二分+当然可以搞一搞。或者用重构树也是可以哒(后面会讲)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,M = 2e5+10;
const int LOGN = 20;
struct Node
{
    int x,y,v;
}a[M+1];

int n,m,s,t,now,fa[N][LOGN+2],val[N],dep[N];
vector<int>e[N];


//////////////////////////////DSU//////////////////////////////////////
struct Dsu {
    int fa[N];
    void init(int x) {for(int i = 1;i<=x;i++) fa[i] = i;}
    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    void merge(int x, int y) {
        int u = find(x), v = find(y);
        if(u == v) return;
        fa[u] = v;
    }
}dsu;
/////////////////////////Kruscal///////////////////////////////////////

void kruskalRebuildTree()
{
    dsu.init(2*n-1);
    sort(a+1, a+1+m, [](const Node& x, const Node& y) {
        return x.v < y.v;
    });
    now = n;
    for(int i = 1;i<=m;i++) {
        ll u = dsu.find(a[i].x), v = dsu.find(a[i].y), w = a[i].v;
        if(u != v) {
            val[++now] = w;
            dsu.merge(u, now);
            dsu.merge(v, now);
            e[now].push_back(u);
            e[now].push_back(v);
        }
    }
}

/////////////////////////LCA/////////////////////////////////////////
void dfs(int u, int from)
{
    dep[u] += dep[from] + 1;
    for(auto v : e[u]) {
        if(v == from) continue;
        fa[v][0] = u;
        dfs(v, u);
    }
}
void lca_init(int now)
{
    for(int j = 1; j < LOGN; j++)
        for(int i = 1; i <= now; i++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
    if(dep[u] < dep[v])   swap(u, v);
    int d = dep[u] - dep[v];
    for(int j = LOGN; j >= 0; j--)
        if(d & (1 << j))
            u = fa[u][j];

    if(u == v)    return u;
    for(int j = LOGN; j >= 0; j--)
    {
        if(fa[u][j] != fa[v][j])
            u = fa[u][j],v = fa[v][j];
    }

    return fa[u][0];
}
/////////////////////////////Main//////////////////////////////////////////////
int main()
{
    cin>>n>>m>>s>>t;
    for(int i = 1;i<=m;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].v;
    }
    kruskalRebuildTree();
    
    //可能是森林
    for(int i = now;i>=1;i--)
    {
        if(!dep[i])
            dfs(i,0);
    }
    lca_init(now);

   int lca  = lca_query(s,t);
    if(!lca)cout<<-1<<"\n";
    else cout<<val[lca]<<"\n";
    return 0;
}

例题2：P2700 逐个击破

题意：花费最小代价，使得给出的个点不连通。

思路：可以反向思考，我们要花费最小代价使得他们不连通，那是不是可以反着思考？

把删除边权小的转化为加入边权大的。用的贪心思想，加入花费大的边。最后答案就是总花费-生成树花费。

❗记得，如果把这条边加进来了，如果有一个是个中的某个，与它相连的端点要标记。因为两个在里面的是不能连起来的，两个有标记的也不能连起来，因为连起来了会使得中的元素连通。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,M = 2e6+10;

struct Node
{
	int x,y,v;
	bool operator <(const Node &A)const{
		return v>A.v;
	}
}a[M+1];

int n,m,k,fa[N+1];
set<int>c;
int cnt = 0;
int find(int x)
{
	if(x==fa[x])return x;
	return fa[x] = find(fa[x]);
}

ll kruskal()
{
	for(int i = 1;i<=n;i++)fa[i] = i;
	sort(a+1,a+1+m);
	ll ans = 0;
	for(int i = 1;i<=m;i++)
	{
		int x = find(a[i].x),y = find(a[i].y);
		if(c.find(x)!=c.end()&&c.find(y)!=c.end())continue;
		if(x!=y)
		{
			fa[x] = y;
			ans += a[i].v;
		}
		if(c.find(x)!=c.end())
			c.insert(y);
		else if(c.find(y)!=c.end())
			c.insert(x);
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	m = n-1;
	ll res = 0;
	for(int i = 1;i<=k;i++)
	{
		int x;
		cin>>x;
		x++;
		
		c.insert(x);
	}
	
	for(int i = 1;i<=m;i++)
	{
		int x,y,v;
		cin>>x>>y>>v;
		x++,y++;
		res += v;
		a[i].x = x,a[i].y = y,a[i].v = v;
	}
	ll ans = kruskal();
	cout<<res-ans<<endl;
	//cout<<"ans = "<<ans<<endl;
	return 0;
}

（2）结合超级源点：

例题1：P1194 买礼物

题意：要买样东西，原价都是。最近促销：买了,再买，就可以只用花,问最少花多少钱？

思路：

将每件物品看作一个结点，物品之间有费用或者优惠为权值的边。
设置一个超级源点号结点，物品与该节点相连表示直接花费元去买。
从向每个结点连权值为的边，其他的按照优惠正常连边
跑

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010,M = 2e6+10;

struct Node
{
    int x,y,v;
    bool operator <(const Node &A)const{
        return v<A.v;
    }
}a[M+1];

int n,m,A,fa[N+1];
int cnt;
int find(int x)
{
    if(x==fa[x])return x;
    return fa[x] = find(fa[x]);
}

ll kruskal()
{
    for(int i = 1;i<=n;i++)fa[i] = i;
    sort(a+1,a+1+cnt);
    ll ans = 0;
    for(int i = 1;i<=cnt;i++)
    {
        int x = find(a[i].x),y = find(a[i].y);
        if(x!=y)
        {
            fa[x] = y;
            ans += a[i].v;
        }
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>A>>n;
    for(int i = 1;i<=n;i++)
    {
        a[++cnt].x = 0;
        a[cnt].y = i;
        a[cnt].v = A;
    }
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            int v;
            cin>>v;
            if(v==0||i>=j)continue;
            a[++cnt].x = i;
            a[cnt].y = j;
            a[cnt].v = v;
        }
    }
    ll ans = kruskal();
    cout<<ans<<endl;
    return 0;
}

例题2：P1550Watering Hole G

思路：和上题思路一样，同样是建立一个超级源点，与它相连的话表示挖一口井，其他供水正常连边，跑就ok啦。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,M = 2e6+10;
int n,cnt,fa[N+1],w[N];
struct Node
{
	int x,y,v;
	bool operator <(const Node &A)const{
		return v<A.v;
	}
}a[M+1];



int find(int x)
{
	if(x==fa[x])return x;
	return fa[x] = find(fa[x]);
}

int kruskal()
{
	for(int i = 1;i<=n;i++)fa[i] = i;
	sort(a+1,a+1+cnt);
	int ans = 0;
	for(int i = 1;i<=cnt;i++)
	{
		int x = find(a[i].x),y = find(a[i].y);
		if(x!=y)
		{
			fa[x] = y;
			ans += a[i].v;
		}
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		cin>>w[i];
		a[++cnt].x = 0,a[cnt].y = i,a[cnt].v = w[i]; 
	}	
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=n;j++)
		{
			int x;
			cin>>x;
			if(i<=j)continue;
			a[++cnt].x = i,a[cnt].y = j,a[cnt].v = x;
		}
	}
	ll ans = kruskal();
	cout<<ans<<endl;
	return 0;
}

例题3：Shichikuji and Power Grid

思路和上面类似，只不过两个之间的花费需要自己计算出来，这里就不赘述啦QAQ。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = 2e3+10;

struct Node
{
	int x,y;
	ll v;
	bool operator <(const Node &A)const{
		return v<A.v;
	}
}a[N*N];

struct ty
{
	int x,y;
}p[N];

int n,m,fa[N+1],cnt,k[N];

int find(int x)
{
	if(x==fa[x])return x;
	return fa[x] = find(fa[x]);
}
set<int>s;
set<pair<int,int>>l;
ll kruskal()
{
	for(int i = 1;i<=n;i++)fa[i] = i;
	sort(a+1,a+1+cnt);
	ll ans = 0;
	for(int i = 1;i<=cnt;i++)
	{
		int x = find(a[i].x),y = find(a[i].y);
		
		
		if(x!=y)
		{
			fa[x] = y;
			ans += a[i].v;
			if(a[i].x==0)
				s.insert(a[i].y);
			else
				l.insert({a[i].x,a[i].y});
		}
	}
	return ans;
}

ll get(ty a,ty b)
{
	return 1ll*abs(a.x-b.x)+abs(a.y-b.y);
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		cin>>p[i].x>>p[i].y;
	}
	for(int i = 1;i<=n;i++)
	{
		int x;
		cin>>x;
		a[++cnt].x = 0,a[cnt].y = i,a[cnt].v = x;
	}
	for(int i = 1;i<=n;i++)
		cin>>k[i];
	for(int i = 1;i<=n;i++)
	{
		for(int j = i+1;j<=n;j++)
		{
			ll cost = k[i]+k[j];
			ll dis = get(p[i],p[j]);
			cost *= dis;
			a[++cnt].x = i,a[cnt].y = j,a[cnt].v = cost;
		}
	}
	cout<<kruskal()<<"\n";
	cout<<s.size()<<"\n";
	for(auto& x:s)
		cout<<x<<" ";
	if(s.size())
		cout<<"\n";
	cout<<l.size()<<"\n";
	for(auto& [x,y]:l)
		cout<<x<<" "<<y<<"\n";
	return 0;
}

（3）Kruskal重构树

分析：重构树是由原树建立起来的一棵二叉树，它将边权信息转换为点权信息。

我们来讲解重构树的经典应用:求图中任意两点间所有路径中最小边权的最大值。

构造方法如下：

按照边权大小排序(按你的需求，如果是找点路径上的边最小值权值的最大值需要按照从大到小排序，因为这样建出来的是小根堆。反之从小到大排序的话，是一个大根堆，可以找到点的简单路径上的的边的最大权值的最小值)
如果 $，$ 以边权的边相连，求出并查集中的代表元。如果他们不在一个集合里面，我们就新建一个结点，设该节点为，点权是【这步实现了边权到点权的转化】，然后把在并查集中的代表元都设为。那么，询问的答案的时候，二者的的点权就是答案。

以下面这题为例，

例题1：P1967 货车运输

按照样例建出的树：

//样例
2 4
3 3
1 1

![image-20230810205713878](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230810205713878.png)

关于正确性？

如果必须要加入边权为的边才能连通，那么答案就是。

按照我们的求法能得到类似答案——它们一开始不相连，在这一步后代表元素（两个根结点）连接权值为的点，才使得它们相连，所以最近公共祖先权值是新结点，权值。而在更后面的连边中，又不会更改它们的的值，那么的权值就是答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,M = 2e5+10;
const int LOGN = 20;
struct Node
{
	int x,y,v;
}a[M+1];

int n,m,q,now,fa[N][LOGN+2],val[N],dep[N];
vector<int>e[N];


//////////////////////////////DSU//////////////////////////////////////
struct Dsu {
	int fa[N];
	void init(int x) {for(int i = 1;i<=x;i++) fa[i] = i;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {
		int u = find(x), v = find(y);
		if(u == v) return;
		fa[u] = v;
	}
}dsu;
/////////////////////////Kruscal////////////////////////////////////

void kruskalRebuildTree()
{
	dsu.init(2*n-1);
	sort(a+1, a+1+m, [](const Node& x, const Node& y) {
		return x.v > y.v;//重构最大生成树
	});
	now = n;
	for(int i = 1;i<=m;i++) {
		ll u = dsu.find(a[i].x), v = dsu.find(a[i].y), w = a[i].v;
		if(u != v) {
			val[++now] = w;
			dsu.merge(u, now);
			dsu.merge(v, now);
			e[now].push_back(u);
			e[now].push_back(v);
		}
	}
}

/////////////////////////LCA///////////////////////////////
void dfs(int u, int from)
{
	dep[u] += dep[from] + 1;
	for(auto v : e[u]) {
		if(v == from) continue;
		fa[v][0] = u;
		dfs(v, u);
	}
}
void lca_init(int now)
{
	for(int j = 1; j < LOGN; j++)
		for(int i = 1; i <= now; i++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
	if(dep[u] < dep[v])   swap(u, v);
	int d = dep[u] - dep[v];
	for(int j = LOGN; j >= 0; j--)
		if(d & (1 << j))
			u = fa[u][j];

	if(u == v)    return u;
	for(int j = LOGN; j >= 0; j--)
	{
		if(fa[u][j] != fa[v][j])
			u = fa[u][j],v = fa[v][j];
	}

	return fa[u][0];
}
///////////////////////////////////////////////////////////////
int main()
{
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].v;
	}
	kruskalRebuildTree();
	
	//可能是森林
	for(int i = now;i>=1;i--)
	{
		if(!dep[i])
			dfs(i,0);
	}
	lca_init(now);

	cin>>q;
	while(q--)
	{
		int s,t;
		cin>>s>>t;
		int lca  = lca_query(s,t);
		if(!lca)cout<<-1<<"\n";
		else cout<<val[lca]<<"\n";
	}
	return 0;
}

例题2：Labyrinth

题意：

给定一张个点，条边的无向图，每条边有一个宽度限制。每个点上有一个糖果，吃了第个点上的糖果会使身体增宽。你也可以经过一个点而不吃掉它的糖果。你能够通过一个边，当且仅当你当前身体的宽度。

你需要从点开始，吃掉所有点上的糖果，但不是必须要返回点。请求出你最大的初始身体宽度，使得你能吃掉所有糖果。

注意初始身体宽度必须是正整数。若无解输出。

思路：瓶颈是每个连通块里面限制最小的边，我们进行重构，重构树的点权就是子树边权的最小值了。那么对于一棵以为根节点的子树，它的情况是怎么样呢？

我们不知道先走左树还是右树，所以都需要考虑。

如果先走左边，那么答案是。为什么呢？因为我需要满足和

那么以上表达式需要同时满足，我们的答案。先走右边是同理的。那么对两边取就行。

最终就是：

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long 
using namespace std;
typedef long long ll;
const int N = 4e5+10,M = 5e5+10;
const int LOGN = 20;
struct Node
{
	int x,y,v;
}a[M+1];

ll n,m,q,now,fa[N][LOGN+2],val[N],dep[N];
vector<int>e[N];
ll ls[N],rs[N],sum[N],c[N],dp[N];

//////////////////////////////DSU//////////////////////////////////////
struct Dsu {
	int fa[N];
	void init(int x) {for(int i = 1;i<=x;i++) fa[i] = i;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {
		int u = find(x), v = find(y);
		if(u == v) return;
		fa[u] = v;
	}
}dsu;
/////////////////////////Kruskal////////////////////////////////////

void kruskalRebuildTree()
{
	dsu.init(2*n-1);
	sort(a+1, a+1+m, [](const Node& x, const Node& y) {
		return x.v > y.v;//重构最大生成树
	});
	now = n;
	for(int i = 1;i<=m;i++) {
		ll u = dsu.find(a[i].x), v = dsu.find(a[i].y), w = a[i].v;
		if(u != v) {
			val[++now] = w;
			dsu.merge(u, now);
			dsu.merge(v, now);
//			e[now].push_back(u);
//			e[now].push_back(v);
			ls[now] = u;
			rs[now] = v;
		}
	}
}


////////////////////////////DP///////////////////////////////////

void dfs(int u)
{
	if(!ls[u]||!rs[u])
	{
		sum[u] = c[u];
		dp[u] = INF;
		return;
	}
	dfs(ls[u]),dfs(rs[u]);
	sum[u] = sum[ls[u]] + sum[rs[u]];
	//               先吃ls[u]
	dp[u] = max(min(dp[rs[u]],val[u])-sum[ls[u]],min(dp[ls[u]],val[u])-sum[rs[u]]);
}

////////////////////////////Main///////////////////////////////////
signed main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)cin>>c[i];
	for(int i = 1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].v;
	}
	kruskalRebuildTree();
	dfs(now);
	if(dp[now]<=0)
		cout<<-1<<"\n";
	else cout<<dp[now]<<"\n";
	
	return 0;
}

例题3:[ARC098F] Donation

这是一道和上一题很像的题目。

题意：

给出一个个点条边的无向连通图，每个点的标号为到, 且有两个权值.第条边连接了点和.

最开始时你拥有一定数量的钱，并且可以选择这张图上的任意一个点作为起始点，之后你从这个点开始沿着给定的边遍历这张图。每当你到达一个点时，你必须拥有至少元。而当你到达了这个点后，你可以选择向它捐献元（当然也可以选择不捐献），当然，你需要保证在每次捐献之后自己剩余的钱。

你需要对所有的个点都捐献一次，求你一开始至少需要携带多少钱。

思路：我们令，即对于点，每个时刻的钱数都应该满足。

我们按照为边权进行重构树，建大根堆。建完树以后考虑如何。

和上题思路类似，差不多就是反过来。

思路：瓶颈是每个连通块里面限制最大的边，我们进行重构，重构树的点权就是子树边权的最大了。那么对于一棵以为根节点的子树，它的情况是怎么样呢？

我们不知道先走左树还是右树，所以都需要考虑。

如果先走左边，那么答案是。为什么呢？因为我需要满足和

那么以上表达式需要同时满足，我们的答案。先走右边是同理的。那么对两边取就行。

最终就是：

还要注意一下叶子节点的处理，对于一个叶子节点，它的.

以上就大功告成啦！你将获得一份和上一次几乎一样滴代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define int long long 
using namespace std;
typedef long long ll;
const int N = 4e5+10,M = 5e5+10;
const int LOGN = 20;
struct Node
{
	int x,y,v;
}a[M+1];

ll n,m,q,now,fa[N][LOGN+2],val[N],dep[N];
vector<int>e[N];
ll ls[N],rs[N],sum[N],c[N],dp[N],A[N],B[N];

//////////////////////////////DSU//////////////////////////////////////
struct Dsu {
	int fa[N];
	void init(int x) {for(int i = 1;i<=x;i++) fa[i] = i;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {
		int u = find(x), v = find(y);
		if(u == v) return;
		fa[u] = v;
	}
}dsu;
/////////////////////////Kruskal////////////////////////////////////

void kruskalRebuildTree()
{
	dsu.init(2*n-1);
	sort(a+1, a+1+m, [](const Node& x, const Node& y) {
		return x.v < y.v;
	});
	now = n;
	for(int i = 1;i<=m;i++) {
		ll u = dsu.find(a[i].x), v = dsu.find(a[i].y), w = a[i].v;
		if(u != v) {
			val[++now] = w;
			dsu.merge(u, now);
			dsu.merge(v, now);
//			e[now].push_back(u);
//			e[now].push_back(v);
			ls[now] = u;
			rs[now] = v;
		}
	}
}


////////////////////////////DP///////////////////////////////////

void dfs(int u)
{
	if(!ls[u]||!rs[u])
	{
		sum[u] = B[u];
		dp[u] = c[u]+B[u];
		return;
	}
	dfs(ls[u]),dfs(rs[u]);
	sum[u] = sum[ls[u]] + sum[rs[u]];
	dp[u] = min(max(dp[rs[u]],val[u])+sum[ls[u]],max(dp[ls[u]],val[u])+sum[rs[u]]);
}

//////////////////////////////Main/////////////////////////////////
signed main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		cin>>A[i]>>B[i];
		c[i] = max(A[i]-B[i],0ll);
	}
	for(int i = 1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y;
		a[i].v = max(c[a[i].x],c[a[i].y]);
	}
	kruskalRebuildTree();
	dfs(now);
	cout<<dp[now]<<"\n";
	return 0;
}

Nannan blog

最小生成树

最小生成树

一、最小生成树定义

二、常见求最小生成树的两种算法

1.Kruscal算法

2.Prim()算法

三、最小生成树常见应用

（1）对于Kruscal原理的理解：

例题1：P1396 营救

例题2：P2700 逐个击破

（2）结合超级源点：

例题1：P1194 买礼物

例题2：P1550Watering Hole G

例题3：Shichikuji and Power Grid

（3）Kruskal重构树

例题1：P1967 货车运输

例题2：Labyrinth

例题3:[ARC098F] Donation