[CF 332D]Theft of Blueprints题解中数学结论证明的翻译

题目:

有一个N<=2000个顶点的边带权简单无向图G。满足:
对于任意k个顶点(1<=k
令集合S的权值为u和S中所有顶点边的权值之和。随机选取集合S,求期望权值。

题解:

这道题主要基于如下结论:
当k>=3时,G是一个含k+1个顶点的完全图。(①)
①的证明仅见于俄文版的官方题解。我们在此将其翻译成中文。(其实是先用google把毛文翻成英文然后再手工把英文翻成中文,哈哈)

证明:


引理1.

图中任意两个不同的顶点恰好有k-1个公共相邻顶点.

引理1的证明:

考虑任意两个不同的顶点s,t。令它们的全部公共相邻顶点为v1,v2,…,vl。如果l>=k,则集合{v1,…,vk}有两个公共相邻顶点s,t,和(*)矛盾。故l<=k-2.考虑顶点集合S={s,t,v1,...,vl},它包含l+2<=k个元素。如果l+2

引理2.

图G包含一个含k+1个顶点的完全子图。

引理2的证明:

考虑集合S={v1,…,vk,vk+1},其中v1,…,vk是图中任意的互异顶点,vk+1是它们的公共相邻顶点。基于集合S,我们给出一个能得到引理2中完全子图的方法:
运行k-1次迭代,第i次我们考虑顶点vi。如果vi和vi+1,vi+2,…,vk均相邻,就进入下一次迭代。否则,考虑集合T={v1 , … , vi-1 , vi+1 , … , vk+1}.根据(*),有一个顶点u和T中所有顶点均相邻(显然u≠vi,因为vi不和j中所有顶点相邻)。我们用u代替vi,进入下一次迭代。显然,在最后一次迭代结束后,我们就得到了一个完全子图,它包含的顶点集合为S。


回到原题目。
下面我们证明对于k>=3,图G是一个含k+1个顶点的完全图。根据引理2,在图G中有一个完全子图,其顶点集合为S={v1,…,vk+1}。我们假设图G中存在一个顶点u∉S。由于S是一个完全图的顶点集合,且由引理1,任意两个顶点恰有k-1个公共相邻顶点,因此对于S中任意两个互异顶点v1,v2,它们的公共相邻顶点均在S中。由于任意k个顶点都恰有一个公共相邻顶点,所以任意i(2<=i<=k-1)个顶点均至少有一个公共相邻顶点。特别地,由于k>=3,故顶点v1,v2,u有一个公共相邻顶点,且该顶点在S中(因为v1,v2的公共相邻顶点均在S中)。若u和S中的两个顶点x,y相邻,则与引理1矛盾(此时x,y有k个公共相邻顶点)。因此,S中存在唯一一个顶点x和u相邻。取S中不同于x的顶点y,则u,x,y三个顶点有一个公共相邻顶点,且它在S中。但这就意味着u和S中的两个顶点相邻,矛盾。
故G中所有点均属于S,G是一个含k+1个顶点的完全图,结论成立。



有了这个结论就很好做了:显然类似C(N,K)这样的组合数都不会太大,所以直接算每个点作为“公共相邻顶点”对答案的贡献即可。时间复杂度O(N^2).

AC代码见下:

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef long double LDB;
const int SIZEN=2010;
LDB C(int n,int m){
	LDB ans=1;
	for(int i=0;i=K){
			ans+=C(snum-1,K-1)*ssum;
		}
	}
	ans/=C(N,K);
	cout<<(LL)(ans+1e-6)<

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注