首页 > 其他分享 >P2619 [国家集训队]Tree I(K 度限制生成树 二分)

P2619 [国家集训队]Tree I(K 度限制生成树 二分)

时间:2022-08-14 17:26:43浏览次数:92  
标签:二分 黑边 Tree 白边 int 权值 need 国家集训队 P2619

P2619 [国家集训队]Tree I

一张 \(n\) 个点 \(m\) 条边的带权无向联通图,每条边是黑色或白色。求一棵最小权的恰好有 \(need\) 条白色边的生成树,题目保证有解。

\(n\le 5\times 10^4,m\le 10^5,val\in[1,100]\)。

\(\color{yellow}{\bigstar\texttt{Trick}}\):这种限制选择 \(need\) 个物品的问题可以考虑 WQS 二分(或者直接叫 二分???)

将所有白边从小到大排序后,每条边权值加上一个 \(x\) 之后再进行最小生成树。

可以发现随着增加值 \(x\) 的增大,我们选择的白边的数量不断减少,完全可以二分找到最接近选择 \(need\) 条白边的那个 \(x\)。

那么我们二分 \(k\),如果发现 \(chose>need\),就增大 \(k\),否则减小 \(k\)。

代码实现的时候有一个细节上的小技巧:二分不一定能够准确的二分到 \(need\),这是因为有白边和黑边权值相同,取到了黑边。

不妨先二分出最接近 \(need\) 的一个 \(x\),由于题目保证有解,此时多出来的白边一定有相同权值的黑边可以代替

为什么?若不存在相同权值的黑边可以代替,我们选择 \(need\) 数量的白边必须要舍弃较小权值 \(wh\) 的白边再选择较大权值 \(bl\) 的黑边,确保交换的 \(bl-wh\) 最小。那么完全可以在二分的时候 \(x\) 变为 \(x+bl-wh+1\),使得二分后这条 \(bl\) 黑边就在 \(wh\) 白边后面(一定不存在新的替换,因为 \(bl-wh\) 最小),这使得二分出选择的白边数量减少 \(1\),与一开始二分出的白边数量最接近与 \(need\) 矛盾,不成立。因此一定存在相同权值的黑边可以替代。

只用将白边与黑边权值相同时钦定白边优先,这样可以将一些的白边“替换”为黑边(贡献不变,意会即可)。

此题代码
// 白边是 0,黑边是 1。
#define Maxn 50005
#define Maxm 100005
int n,m,ned,cnt0,cnt1,ans=inf,Now,mid;
int fa[Maxn];
struct EDGE
{
	int u,v,c,opt;
	EDGE(int U=0,int V=0,int C=0,int OPT=0):u(U),v(V),c(C),opt(OPT){}
	bool friend operator < (EDGE x,EDGE y)
		{ return (x.c!=y.c)?x.c<y.c:(x.opt<y.opt); }
}wh[Maxm],bl[Maxm],tmp[Maxm];
int Find(int x){ return (fa[x]==x)?x:(fa[x]=Find(fa[x])); }
inline bool merge(int x,int y)
{
	x=Find(x),y=Find(y);
	if(x!=y) { fa[x]=y; return true; }
	return false;
}
inline bool check()
{
	int used=0;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=cnt0;i++) wh[i].c+=mid;
	merge(bl+1,bl+cnt1+1,wh+1,wh+cnt0+1,tmp+1);
	for(int i=1;i<=m;i++) if(merge(tmp[i].u,tmp[i].v))
		Now+=tmp[i].c,used+=(tmp[i].opt^1);
	for(int i=1;i<=cnt0;i++) wh[i].c-=mid;
	Now-=mid*ned;
	return used>=ned;
}
int main()
{
	n=rd(),m=rd(),ned=rd();
	for(int i=1,s,t,c,col;i<=m;i++)
	{
		s=rd()+1,t=rd()+1,c=rd(),col=rd();
		if(!col) wh[++cnt0]=EDGE(s,t,c,0);
		else bl[++cnt1]=EDGE(s,t,c,1);
	}
	sort(wh+1,wh+cnt0+1),sort(bl+1,bl+cnt1+1);
	int nl=-101,nr=101;
	while(nl<=nr)
	{
		mid=(nl+nr)>>1,Now=0;
		if(check()) nl=mid+1,ans=Now;
		else nr=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}

P5633 最小度限制生成树

其实就是上面的弱化为限制单点相邻的白边数量,但是增添了无解的情况

无解可以这样判断:将于这个点相邻的边全部断开,如果分开后连通块数量 \(>need\) 则无解,其他一定有解。

标签:二分,黑边,Tree,白边,int,权值,need,国家集训队,P2619
From: https://www.cnblogs.com/EricQian/p/16585805.html

相关文章

  • [atAGC025E]Walking on a Tree
    设第$i$条边被$c_{i}$条路径覆盖,显然答案上界为$\sum\min(c_{i},2)$事实上,上界可以被取到,考虑以下构造——取树上的一个叶子,假设其到父亲的边为$i$,对其分类讨论:1.若$c_{......
  • Atcoder Grand Contest 025 E - Walking on a Tree(欧拉回路)
    Atcoder题面传送门打个表发现答案等于每条边被覆盖的次数与\(2\)取min之和,考虑如何构造这个上界。首先考虑树是以\(1\)为中心的菊花图,且任意\(A_i,B_i\ne1\)的......