P5633 最小度限制生成树 题解
Foreverxxx · · 题解
广告：一名Blink的博客
感谢出题人 Inkyo 大佬，让我学到了很多。
正文
暴力做法
记录 s 连出去的所有边，每次枚举 k 条边出来，求生成树，判断是否合法并且更新答案。
正确做法： wqs 二分
不要被新算法吓到！很容易理解的。
关于 wqs 二分的详解，可以参考这两篇洛谷日报：
#366 Flying2018 wqs二分&闵可夫斯基和学习笔记
#354 Leap_Frog wqs二分 学习笔记
我的做法只是参考了 wqs 二分的思想，做题时想不到很正常，毕竟做题时现想出算法不容易。
既然二分有多种形式，也可以看出此题的答案具有单调性，我们可以大胆地对 s 的所有出边进行二分处理。
怎么二分呢？
为了满足 k 条边的限制条件，同时此题又与最小生成树有关，大胆假设以下思路：
我们可以考虑二分一个偏移量
拿样例来辅助理解，其中要求点 1 连的边数量为 1。
这是原来的图：
假设此时二分的
而我们对新图做一次 Kruskal，求得的生成树就会是这个样子：
可以发现，节点 1 已经连了超过 1 条边，说明我们需要调高
那么求得的最小生成树便是：
此时 1 刚好连了 1 条边，我们需要再次调大
对于判断是否有解，有以下几种情况需要考虑：
1、连向 s 的节点的边不足 k 条。
2、原图不连通。
3、最终二分出的
最后是 AC 代码，有些细节会在代码中提到，帮助理解最小度限制生成树。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int sss=0;
char chh=getchar();
while(chh>'9'||chh<'0') chh=getchar();
while(chh<='9'&&chh>='0'){
sss=sss*10+chh-'0';
chh=getchar();
}
return sss;
}
int n,m,s,k;
struct node{
int u,v,w;
};
int tot_s=0,tot_nots=0;
node edge_s[500004];//用来存储连向s的边
node edge_nots[500004];//用来存储没有连向s的边
node edge[500004];//用来存储每次二分时，连向s的边加上偏移量后所有的边，以便之后的 Kruskal求最小生成树
vector<int> to[50004];//判断是否联通
bool vis[50004];
int fa[50004];
int sum_value=0;//统计加上偏移量之后的最小生成树的权值和，输出的答案只需要减去 k*mid即可
bool cmp(node x,node y){//按照权值排序
return x.w<y.w;
}
void bfs(){
//bfs对所有扫到的边进行标记操作，用来判断原来的图是否联通
queue<int> q;
q.push(1);
vis[1]=1;
while(!q.empty()){
int x=q.front(); q.pop();
int len=to[x].size();
for(register int i=0;i<len;i++){
int u=to[x][i];
if(vis[u]) continue;
vis[u]=1;
q.push(u);
}
}
}
int find(int x){//并查集基本操作
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void add_delta(int x){
for(register int i=1;i<=tot_s;i++) edge_s[i].w+=x;//对所有连向 s 的边加上偏移量
/*
接下来时类似于归并排序的操作
两种边，用两个指针记录，从而 o(m) 将所有边排好序统计到 edge 中
*/
int i=1,j=1,k=0;
while(i<=tot_s&&j<=tot_nots){
if(edge_s[i].w<=edge_nots[j].w){
k++;
edge[k]=edge_s[i];
i++;
}
else {
k++;
edge[k]=edge_nots[j];
j++;
}
}
while(i<=tot_s){
k++;
edge[k]=edge_s[i];
i++;
}
while(j<=tot_nots){
k++;
edge[k]=edge_nots[j];
j++;
}
for(register int i=1;i<=tot_s;i++) edge_s[i].w-=x;//统计完后还原原来的图
}
bool check(int x){
for(register int i=1;i<=n;i++) fa[i]=i;//初始化并查集
add_delta(x);
sum_value=0;
int cnt=0;//记录此时s有多少条连边
int waiting=n;//一共有n个点需要连边
for(register int i=1;i<=m;i++){
if(waiting==1) break;
int fau=find(edge[i].u),fav=find(edge[i].v);
if(fau==fav) continue;
if(edge[i].u==s||edge[i].v==s) cnt++;//如果这条边有节点为s，则 cnt++
waiting--;//少了一个点需要加入生成树
sum_value+=edge[i].w;//统计生成树总的权值
fa[fau]=fav;//并查集合并操作
}
return cnt>=k;
}
bool check_ans(int x){
//对最终的二分结果进行判断，和上面的check函数差不多，只不过 return 条件变为了 cnt==k
for(register int i=1;i<=n;i++) fa[i]=i;
add_delta(x);
sum_value=0;
int cnt=0;
int waiting=n;
for(register int i=1;i<=m;i++){
int fau=find(edge[i].u),fav=find(edge[i].v);
if(fau==fav) continue;
if(edge[i].u==s||edge[i].v==s) cnt++;
waiting--;
sum_value+=edge[i].w;
fa[fau]=fav;
if(waiting<=1) break;
}
return cnt==k;
}
int main(){
n=read(),m=read(),s=read(),k=read();
int uu,vv,ww;
for(register int i=1;i<=m;i++){
uu=read(),vv=read(),ww=read();
if(uu==s||vv==s){
tot_s++;
edge_s[tot_s].u=uu;
edge_s[tot_s].v=vv;
edge_s[tot_s].w=ww;
}
else {
tot_nots++;
edge_nots[tot_nots].u=uu;
edge_nots[tot_nots].v=vv;
edge_nots[tot_nots].w=ww;
}
to[uu].push_back(vv);
to[vv].push_back(uu);//用来判断是否联通
}
if(tot_s<k){
cout<<"Impossible";
return 0;
}
bfs();
for(register int i=1;i<=n;i++){
if(!vis[i]){//如果bfs之后有点没有被扫到，则说明图并不联通
cout<<"Impossible";
return 0;
}
}
sort(edge_s+1,edge_s+tot_s+1,cmp);//先初始化对两种边进行排序,能够优化掉add操作的一个log
sort(edge_nots+1,edge_nots+tot_nots+1,cmp);
int l=-300001,r=300001,mid;//最小值：s所有出边权值均为0 最大值：s所有出边的权值为图中的最大
//注意二分的区间应与题目描述对应，否则可能被卡常
int ans=0;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
l=mid+1;
ans=mid;//注意每次判断可行后直接更新ans，不需要进行大小比较操作，否则会造成sum_value与ans不对应，很容易理解
//即ans和sum_value应该同时更新
}
else r=mid-1;
}
if(!check_ans(ans)){
cout<<"Impossible";
return 0;
}
cout<<sum_value-k*ans;
return 0;
}