[图论]最小生成树
最小生成树
一、最小生成树定义
最小生成树定义：在一张带权无向图中，最小生成树是一棵生成树，它的边权值之和最小。
什么是生成树？
生成树是一棵包含原图所有顶点的树，它的边的集合是原图的一个子集，并且任意两点之间有且只有一条简单路径。
二、常见求最小生成树的两种算法
1.Kruscal算法
\(Kruscal\)算法的主要思想是：按照边权的大小依次选边，如果这条边的两个端点没在一个连通块里面，那就把这条边加到最小生成树的边集里面。
具体步骤：
- 边按照权值排序
- 按照顺序依次加边
- 重复以上操作直到有最小生成树边集里面有\(n-1\)条边为止。
复杂度：\(O(m\log m)\),其中\(m\)为边数。
注意：\(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算法
\(Prim\)算法是主要思想是：从任意一个顶点开始，每次选择一个与当前连通块相邻的权值最小的边，并把它加到最小生成树的边集里面，直到所有顶点都加入。
具体步骤：
- 随机选择一个顶点作为起点
- 将于起点相邻的边按照边权从小到大排序，并选择权值最小的边加入到最小生成树的边集里面。
- 将新加入的点加入到连通块中，并将于它相邻的边按照边权从小到大排序。
- 重复2，3步骤直到所有点是加入。
时间复杂度：\(O(n^2+m)\),其中\(n\)为顶点数。若用堆优化时间复杂度\(O((n+m)\log n)\)
注意：\(Prim\)存的是双向边,适合稠密图。
朴素写法：\(O(n^2+m)\)
完整写法，不一定是连通图情况
#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;
}
堆优化写法\(O((n+m)\log n)\)
\(dijkstra\) 和 $prim $的区别
差别只在于最后循环体内的松弛操作。
最小生成树只关心所有边的和最小，所以有\(v.key = w(u, v)\)，即每个点直连其他点的最小值（最多只有两个节点之间的权值和）
最短路径树只搜索权值最小，所以有\(v.key = w(u, v) + u.key\)，即每个点到其他点的最小值（最少是两个节之间的权值和）
#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 营救
题意：给你起点\(s\)和终点\(t\)，问你在通往\(s\)到\(t\)的路径上最大拥挤度最小是多少？
思路：因为我们知道用\(Kruscal\)建立最小生成树的时候是从小往大加边的，那么第一次加入且使得\(s\)和\(t\)连通的边就是答案了。
#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;
}
当然了，这道题的解法还有很多。求最大值最小，二分+\(dp\)当然可以搞一搞。或者用\(Kruscal\)重构树也是可以哒(后面会讲)。
#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 逐个击破
题意：花费最小代价，使得给出的\(k\)个点不连通。
思路：可以反向思考，我们要花费最小代价使得他们不连通，那是不是可以反着思考？
把删除边权小的转化为加入边权大的。用\(Kruscal\)的贪心思想，加入花费大的边。最后答案就是总花费-生成树花费。
❗记得，如果把这条边加进来了，如果有一个是\(k\)个中的某个，与它相连的端点要标记。因为两个在\(k\)里面的是不能连起来的，两个有标记的也不能连起来，因为连起来了会使得\(k\)中的元素连通。
#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 买礼物
题意：要买\(b\)样东西，原价都是\(a\)。最近促销：买了\(I\),再买\(J\)，就可以只用花\(K_{I,J}\),问最少花多少钱？
思路：
- 将每件物品看作一个结点，物品之间有费用或者优惠为权值的边。
- 设置一个超级源点\(0\)号结点，物品与该节点相连表示直接花费\(a\)元去买。
- 从\(0\)向每个结点连权值为\(a\)的边，其他的按照优惠正常连边
- 跑\(Kruskal\)
#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
思路：和上题思路一样，同样是建立一个超级源点，与它相连的话表示挖一口井，其他供水正常连边，跑\(Kruskal\)就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重构树
分析：\(Kruskal\)重构树是由原树建立起来的一棵二叉树，它将边权信息转换为点权信息。
我们来讲解\(Kruskal\)重构树的经典应用:求图中任意两点间所有路径中最小边权的最大值。
构造方法如下：
- 按照边权大小排序(按你的需求，如果是找点\(x\)路径上的边最小值权值的最大值需要按照从大到小排序，因为这样建出来的是小根堆。反之从小到大排序的话，是一个大根堆，可以找到点\(x\)的简单路径上的的边的最大权值的最小值)
- 如果\(x，y\)以边权\(v\)的边相连，求出并查集中\(x,y\)的代表元\(fx,fy\)。如果他们不在一个集合里面，我们就新建一个结点，设该节点为\(u\)，点权是\(w\)【这步实现了边权到点权的转化】，然后把\(fx,fy\)在并查集中的代表元都设为\(u\)。那么，询问\(x,y\)的答案的时候，二者的\(lca\)的点权就是答案。
以下面这题为例，
例题1：P1967 货车运输
按照样例建出的树：
//样例
1 2 4
2 3 3
3 1 1
关于正确性？
如果\(x,y\)必须要加入边权为\(w\)的边才能连通，那么答案就是\(w\)。
按照我们的求法能得到类似答案——它们一开始不相连，在这一步后代表元素（两个根结点）连接权值为 \(w\)的点，才使得它们相连，所以最近公共祖先权值是新结点，权值 \(w\)。而在更后面的连边中，又不会更改它们的\(lca\)的值，那么\(lca\)的权值就是答案。
#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
题意：
给定一张 \(n\) 个点，\(m\) 条边的无向图，每条边有一个宽度限制 \(w_i\)。每个点上有一个糖果，吃了第 \(i\) 个点上的糖果会使身体增宽 \(c_i\)。你也可以经过一个点而不吃掉它的糖果。你能够通过一个边 \(i\)，当且仅当你当前身体的宽度 \(\le w_i\)。
你需要从点 \(1\) 开始，吃掉所有点上的糖果，但不是必须要返回点 \(1\)。请求出你最大的初始身体宽度，使得你能吃掉所有糖果。
注意初始身体宽度必须是正整数。若无解输出 \(-1\)。
思路：瓶颈是每个连通块里面限制最小的边，我们进行\(Kruscal\)重构，重构树的点权就是子树边权的最小值了。那么对于一棵以\(u\)为根节点的子树，它的情况是怎么样呢？
我们不知道先走左树还是右树，所以都需要考虑。
如果先走左边，那么答案是\(min(dp[rs[u]],val[u])-sum[ls[u]]\)。为什么呢？因为我需要满足\(dp[u]+sum[ls[u]]\le val[u]\)和\(dp[u]+sum[ls[u]]\le dp[rs[u]]\)
那么以上表达式需要同时满足，我们的答案\(dp[u] = min(dp[rs[u]],val[u])-sum[ls[u]]\)。先走右边是同理的。那么对两边取\(max\)就行。
最终就是：\(dp[u] = max(min(dp[rs[u]],val[u])-sum[ls[u]],min(dp[ls[u]],val[u])-sum[rs[u]])\)
#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
这是一道和上一题很像的题目。
题意：
给出一个\(N\)个点\(M\)条边的无向连通图，每个点的标号为\(1\)到\(n\), 且有两个权值\(A_i,B_i\).第\(i\)条边连接了点\(u_i\)和\(v_i\).
最开始时你拥有一定数量的钱，并且可以选择这张图上的任意一个点作为起始点，之后你从这个点开始沿着给定的边遍历这张图。每当你到达一个点\(v\)时，你必须拥有至少\(A_v\)元。而当你到达了这个点后，你可以选择向它捐献\(B_v\)元（当然也可以选择不捐献），当然，你需要保证在每次捐献之后自己剩余的钱\(\geq 0\)。
你需要对所有的\(n\)个点都捐献一次，求你一开始至少需要携带多少钱。
思路：我们令\(C[i] = max(A[i]-B[i],0)\)，即对于点\(i\)，每个时刻的钱数都应该满足\(\ge C[i]\)。
我们按照\(C[i]\)为边权进行\(Kruskal\)重构树，建大根堆。建完树以后考虑如何\(DP\)。
和上题思路类似，差不多就是反过来。
思路：瓶颈是每个连通块里面限制最大的边，我们进行\(Kruscal\)重构，重构树的点权就是子树边权的最大了。那么对于一棵以\(u\)为根节点的子树，它的情况是怎么样呢？
我们不知道先走左树还是右树，所以都需要考虑。
如果先走左边，那么答案是\(max(dp[rs[u]],val[u])+sum[ls[u]]\)。为什么呢？因为我需要满足\(dp[u]-sum[ls[u]]\ge val[u]\)和\(dp[u]-sum[ls[u]]\ge dp[rs[u]]\)
那么以上表达式需要同时满足，我们的答案\(dp[u] = max(dp[rs[u]],val[u])+sum[ls[u]]\)。先走右边是同理的。那么对两边取\(max\)就行。
最终就是： $ dp[u]=min(max(dp[rs[u]],val[u])+sum[ls[u]],max(dp[ls[u]],val[u])+sum[rs[u]])$
还要注意一下叶子节点的处理，对于一个叶子节点，它的\(dp[u] = C[i]+B[i],sum[u] = B[i]\).
以上就大功告成啦！你将获得一份和上一次几乎一样滴代码\((bushi)\)
#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;
}