CF125E MST Company 题解
题目链接:CF125E MST Company
题意:
给你一个有 $n$ 个节点,$m$ 条边的带权无向图,你需要求得一个生成树,使边权总和最小,且满足节点 $1$ 正好连了 $k$ 条边。
输出最优方案所选的边
$1 \le n,k \le 5000,~0 \le m \le 10^5,~1 \le w \le 10^5$
这道题的加强版,题解(下文我摘抄过来了一部分,反正都是我写的)
我们把与 $s$ 相连的所有边标记为白边,其他边为黑边
然后问题就转化为了选恰好 $k$ 条白边的最小花费
考虑wqs二分,最好用归并优化一下
这题的难点在无解的情况如何判断
白边不够用,如果与 $s$ 相连的边小于 $k$ 条,无解
黑边不够用,也就是生成树不得不包括大于 $k$ 条白边,无解
那道弱化版的题目只要求输出最优解的花费
但是我们都知道wqs二分的那个切线可能同时切到多个点
然后我的代码的写法是权值相等时优先取白边
所以答案中选了 $k$ 条白边后就不要再选白边了(当然这样不会改变权值)
时间复杂度 $O(n\log n + n\log {\max\{w_i\}})$
可以通过所有的hack数据,请放心食用 qwq
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*_p1,*_p2;
char readchar()
{
if(_p1==_p2)_p1=buf1,_p2=buf1+fread(buf1,1,SIZ,stdin);
return _p1==_p2?EOF:*_p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(5e3+15)
#define M (int)(1e5+15)
int n,m,k,p1,p2,cnt,sum,ok,mx,f[N];
struct Edge{int u,v,w,c,id;}e[M],c1[M],c2[M];
void init(){for(int i=1; i<=n; i++)f[i]=i;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int cmp(Edge a,Edge b){return a.w<b.w;}
int merge(int u,int v)
{
u=find(u);v=find(v);
if(u==v)return 0;
return f[u]=v,1;
}
void proc(int mid)
{
for(int d=1; d<=p1; d++)
c1[d].w-=mid;
int i=1,j=1,pos=0;
for(; i<=p1; i++)
{
while(c1[i].w>c2[j].w&&j<=p2)
e[++pos]=c2[j++];
e[++pos]=c1[i];
}
while(j<=p2)e[++pos]=c2[j++];
for(int d=1; d<=p1; d++)
c1[d].w+=mid;
}
void kruskal(int mid)
{
proc(mid); cnt=sum=0;
int tmp=0; init();
for(int i=1; i<=m&&tmp<n; i++)
{
if(ok)
{
int u=e[i].u,v=e[i].v;
if(find(u)!=find(v))
{
if(cnt+e[i].c>k)continue;
else
{
merge(e[i].u,e[i].v);
cnt+=e[i].c,sum+=e[i].w,++tmp;
write(e[i].id);
pc(" \n"[tmp==n-1]);
}
}
}else if(merge(e[i].u,e[i].v))
cnt+=e[i].c,sum+=e[i].w,++tmp;
}
}
signed main()
{
read(n);read(m);read(k);
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
if(u==1||v==1)
c1[++p1]={u,v,w,1,i},mx=max(mx,w);
else c2[++p2]={u,v,w,0,i};
}
if(p1<k)return puts("-1"),0;
sort(c1+1,c1+p1+1,cmp);sort(c2+1,c2+p2+1,cmp);
int l=-mx-5,r=mx+5;
kruskal(l); if(cnt>k)return puts("-1"),0;
while(l<r)
{
int mid=(l+r)>>1;
kruskal(mid);
if(cnt>=k) r=mid;
else l=mid+1;
}
// write(sum+k*l);pc('\n');
write(n-1);pc('\n');
ok=1;kruskal(l);
return 0;
}