题解 CF125E 【MST Company】
frankchenfu
2018-03-26 12:54:52
## 题意简述
这道题需要我们求一种特殊的最小生成树。给定一个有$n$个节点和$m$条边的图，找出一个生成树满足从根节点$1$直接连向其余节点的边要恰好是$k$条，在此条件下生成树的权值和最小。
## 分析
### 算法1
理论上好像拓展次小生成树的算法（$k$小生成树）是可以写出来的，但是复杂度大约是$O(n^3)$，所以不能通过。（如果有dalao用这种方法写出复杂度更低的，那么就当我这句话没说）。
### 算法2
我们考虑使用最小生成树的`Kruskal`算法作为基础。`Kruskal`需要对边进行排序，然后从小到大贪心选择。为了保证与根的连边数量符合条件，我们是不是可以考虑对这些边“动一些手脚”呢？
于是我们把所有的边分成两类，一类是与根有联系的边集$E_1$，另一类是其他普通边构成的边集$E_2$。然后我们可以尝试给$E_1$中的边全部加上一个或正或负值$p$，这样就可以改变这些边排序时原有的次序。
比如，如果我们给每一条边都加上$-100001$的权值，那么所有$E_1$中的边都排在$E_2$的边之前（数据范围$1\le w_i\le 10^5$）；如果加上$100001$的权值，那么所有$E_1$中的边都排在$E_2$的边之后。如果这个$p$的绝对值较小，那么就有可能使$E_1$中边的排名稍微靠前或靠后一点。
然后我们就可以考虑二分这个值$p$，使得它刚好与根的连边有$k$条。二分的单调性是显然的，因为如果同时给$E_1$中的边加上$p$之后，$E_1$内和$E_2$内各自的边相对顺序不变，并且把$E_1$边权变小之后排名不会变后。所以这个结果是具有单调性的。
于是我们就可以通过二分查找到一个合适的$p$是的根节点度限制恰好为$k$。但是注意到有的时候这个算法二分出的结果并不是恰好$k$条，而我们要优先保证有解。所以我们最好要特判一下，然后按照上面的算法选择，同时加入“如果已经大于$k$，那么就略过此边”。最后代码中特判一些特殊情况即可。代码如下：
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
const int MAXN=5010;
const int MAXM=100010;
struct edge{
int u,v;double w;
void adde(int u,int v,double w){
this->u=u;
this->v=v;
this->w=w;
}
}e[MAXM];
struct vect{
int val[MAXM],tp;
vect(){
tp=0;
}
void clear(){
tp=0;
}
void push(int v){
val[++tp]=v;
}
}res;
int n,m,k,p,ans=2147483647;
int ord[MAXM],cap;
struct ufs{
int father[MAXN],sz;
void resize(int n){
sz=n;
for(int i=1;i<=n;i++)
father[i]=i;
}
int getfather(int x){
if(x==father[x])
return father[x];
return father[x]=getfather(father[x]);
}
}sol;
double wet;//weight
bool cmp_wet(const int &l,const int &r){
double lans=e[l].w,rans=e[r].w;
if(e[l].u==1)
lans+=wet;
if(e[r].u==1)
rans+=wet;
return lans<rans;
}
void check(){//kruscal
sol.resize(n);res.clear();cap=0;
std::sort(ord+1,ord+m+1,cmp_wet);//按照权重排序.
for(int i=1;i<=m;i++){
int a=sol.getfather(e[ord[i]].u),b=sol.getfather(e[ord[i]].v);
if(a==b)
continue;
sol.father[a]=b;
if(e[ord[i]].u==1)
cap++;
res.push(ord[i]);
if(--sol.sz==1)
return;
}
}
void calc(){
sol.resize(n);res.clear();cap=0;
std::sort(ord+1,ord+m+1,cmp_wet);//按照权重排序.
for(int i=1;i<=m;i++){
int a=sol.getfather(e[ord[i]].u),b=sol.getfather(e[ord[i]].v);
if(a==b)
continue;
if(e[ord[i]].u==1)
cap++;
if(cap>k){
cap--;
continue;
}
sol.father[a]=b;
res.push(ord[i]);
if(--sol.sz==1)
return;
}
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++){
int u,v;double w;scanf("%d%d%lf",&u,&v,&w);
if(u>v)
std::swap(u,v);
e[i].adde(u,v,w);
if(u==1)
p++;
}
if(p<k||(n>1&&!k)){
puts("-1");
return 0;
}
for(int i=1;i<=m;i++)
ord[i]=i;
check();
if(sol.sz>1)//不连通
{
puts("-1");
return 0;
}
double l=-1e5,r=1e5+0.5;
for(;;)
{
if(cap==k)
break;
if(l+0.1>r&&cap>k)
break;
double mid=(l+r)/2.0;
wet=mid;check();
if(cap<k)
r=mid;
else
l=mid;
}
if(cap!=k)
calc();
printf("%d\n",res.tp);
for(int i=1;i<=res.tp;i++)
printf("%d ",res.val[i]);
return 0;
}
```