CF125E题解
jiqimao
2019-12-14 17:21:27
关于基础的WQS二分我们在此不再赘述,关于蒟蒻对WQS的理解可以看蒟蒻的[博客](https://prutekoi.github.io/post/xue-xi-bi-ji-wqs-er-fen-tu-you-hua/)。
EndSaH大佬已经hack了显然不对的一些WQS二分,并给出了自己的一种构造方案,不过是利用了这题限制1的度数的一些性质。
我们现在可以给出这题的超集[P2619 [国家集训队2]Tree I ](https://www.luogu.com.cn/problem/P2619)的方案构造方式。
> 给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
用WQS二分可以二分出一个斜率 $k$,已知need这个点也在这条直线上。于是把所有白边都加上权值 $k$。（注意WQS二分的过程已经结束了,下面是构造方案）
我们可以用最多白边和最少白边策略分别跑一遍克鲁斯卡尔。
首先通过拟阵的一些性质可以得出最小生成树中白边数量的可能情况是连续的。有了最大值和最小值之后我们就可以判是否无解了（区间不包含 $need$ 即无解）。那么接下来就是如何构造方案。
我们知道最小生成树边权相同的边之间才会互相替换,且同一边权的边用的数量是固定的。于是我们可以按照边权从小到大分批次地考虑这些边。不同批次之间的边相当于是独立的。
在上面求最少白边时我们可以顺带求出在每一批次中一定需要选的白边有哪些,那么我们构造时就先把这些边连上(不然构不成最小生成树)。
当前批次中剩下的边可以全都选黑边(但是有可能之后选最多数量的白边也凑不够 $need$ 条白边了)。如何抉择剩下的边怎么选呢?
我们之前求最多白边时可以对于每个边权 $x$,求出在满足最小生成树条件下边权大于 $x$ 的边最多选多少白边,设为 $R[x]$。
那么在构造时对于 $x$ 边权的不必要的白边只要加到 $now+R[x]==need$ 即可,然后这批次就可以只加黑边。
这样构造到所有批次都结束之后即可得到合法的解。
应该对于一般的WQS二分也可以套用这样的思路构造方案。
我的代码可以过掉所有的hack数据呦,请放心食用。
代码很丑...
```c++
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n,m,need,n1,n2,x[N],y[N],z[N],c1[N],c2[N],f[N],s[N],R[N],ll,rr;bool flag;
bool cmp(int x,int y){return z[x]<z[y];}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
vector<int>v[N],Ans;
bool merge(int id){
int fx=find(x[id]),fy=find(y[id]);
if(fx==fy)return 0;
if(flag)Ans.push_back(id);
if(s[fx]>s[fy])swap(fx,fy);
f[fx]=fy;s[fy]+=s[fx];return 1;
}
int main(){
scanf("%d%d%d",&n,&m,&need);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x[i],&y[i],&z[i]);
(x[i]==1||y[i]==1?c1[++n1]:c2[++n2])=i;
}
sort(c1+1,c1+n1+1,cmp);sort(c2+1,c2+n2+1,cmp);
int l=-5e8,r=5e8,ans=-1e9;
while(l<=r){
int mid=(l+r)>>1,i=1,j=1,now=0;
for(int k=1;k<=n;k++)f[k]=k,s[k]=1;
while(i<=n1||j<=n2)
if(i>n1||(j<=n2&&z[c2[j]]<z[c1[i]]+mid))merge(c2[j++]);
else now+=merge(c1[i++]);
if(now>=need)ans=mid,l=mid+1;
else r=mid-1;
}
if(ans==-1e9)puts("-1");
for(int i=1;i<=n1;i++)z[c1[i]]+=ans;
int i=1,j=1,now=0;
for(int k=1;k<=n;k++)f[k]=k,s[k]=1;
for(int k=-1e9;i<=n1||j<=n2;){
if(i>n1||(j<=n2&&z[c2[j]]<=z[c1[i]])){
if(z[c2[j]]!=k)k=z[c2[j]];
merge(c2[j++]);
}
else{
if(z[c1[i]]!=k)k=z[c1[i]];
if(merge(c1[i])){
if(k>=1&&k<=1e5)v[k].push_back(c1[i]);
now++;
}
i++;
}
}
ll=now;now=0;i=j=1;if(ll>need)puts("-1"),exit(0);
for(int k=1;k<=n;k++)f[k]=k,s[k]=1;
for(int k=-1e9;i<=n1||j<=n2;){
if(i>n1||(j<=n2&&z[c2[j]]<z[c1[i]])){
if(z[c2[j]]!=k){
if(k>=1&&k<=1e5)R[k]=now;
k=z[c2[j]];if(k>=1&&k<=1e5)R[k]=1e9;
}
merge(c2[j++]);
}
else{
if(z[c1[i]]!=k){
if(k>=1&&k<=1e5)R[k]=now;
k=z[c1[i]];if(k>=1&&k<=1e5)R[k]=1e9;
}
now+=merge(c1[i++]);
}
}
rr=now;now=0;i=j=1;flag=1;
for(int k=1;k<=1e5;k++)R[k]=max(0,rr-R[k]);
for(int k=1;k<=n;k++)f[k]=k,s[k]=1;
for(int k=-1e9;i<=n1&&j<=n2;){
k=min(z[c1[i]],z[c2[j]]);
if(k<1||k>1e5){
while(i<=n1&&z[c1[i]]==k)
now+=merge(c1[i++]);
}
else{
for(int l=0;l<v[k].size();l++)now+=merge(v[k][l]);
while(now+R[k]<need)now+=merge(c1[i++]);
while(j<=n2&&z[c2[j]]==k)merge(c2[j++]);
while(i<=n1&&z[c1[i]]==k)now+=merge(c1[i++]);
}
}
while(i<=n1)now+=merge(c1[i++]);
while(j<=n2)merge(c2[j++]);
printf("%d\n",n-1);
for(int i=0;i<Ans.size();i++)printf("%d ",Ans[i]);
return 0;
}
```