[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)<

题目：

题解：

证明：

引理1.

引理1的证明：

引理2.

引理2的证明：

发表回复 取消回复

发表回复取消回复