题解 CF332D 【Theft of Blueprints】
whiteqwq
·
·
题解
CF332D Theft of Blueprints解题报告
更好的阅读体验
题意
- 给定一个n个点带边权的无向图，且满足对于任意大小为k的点集S都满足有且仅有一个点p\notin S（下文称之为中间点）与S中所有点存在一条边。
- 定义一个点集的权值为这个点集对应的点p与这个点集所有点的边权值之和。
- 求任意一个大小为k的点集的权值期望，答案向下取整。
- 数据范围2\leqslant n\leqslant 2000,1\leqslant k\leqslant n-1。
分析
比较好玩的一道题。
k=1的情况
### $k=2$的情况
我们枚举每一个中间点$p$，并枚举这个中间点的每一条边$(p,x)$，那么不难发现这条边造成贡献当且仅当另一个点$y$与$x$成为点集，且$y$与$p$有一条边。设$p$的度数为$cnt$，这条边权值为$v$，则这条边造成的贡献为$(cnt-1)\times v$。
时间复杂度：$O(n^2)$。
### $k\geqslant 3$的情况
引理1：当$k\geqslant 3$时且满足上述条件时，原图任意两个结点都恰好有$k-1$个公共相邻结点。
证明：
设原图内两点公共相邻结点数量为$v$，那么有：
如果$v\geqslant k$，那么这两个结点的公共相邻结点可以形成一个大小为$k$的集合，且两个点都是中间点，不符合题意，故$v<k$。
如果$v<k-1$，那么这两个点与它们公共相邻顶点构成的点集$T$大小小于等于$k$，取任意一个大小为$k$的集合，满足$T$为该集合的子集，则可以得到一个新的点$d\notin T$，且$d$与这两个点均存在一条边，也就是说两个点存在了一个新的公共相邻结点，故$v\geqslant k-1$。
因此$v=k-1$，结论成立。
引理2：当$k\geqslant 3$时且满足上述条件时，原图包含一个$k+1$个点的完全图。
证明：我们取任意相连的两点$a_1,a_2$，不难找到一个包含$a_1,a_2$的集合，它的中间点为$a_3$，那么$a_1$与$a_3$，$a_2$与$a_3$均存在一条边，同理寻找一个包含$a_{1\cdots3}$的集合中间点为$a_4$，一直寻找到$a_{k+1}$，不难发现这$k+1$个点构成了一个$k+1$个点的完全图。
引理3：当$k\geqslant 3$且满足上述条件时，仅$k+1$个点的完全图满足条件。
证明：根据引理$2$可得原图包含一个$k+1$个点的完全图$a_{1\cdots k+1}$。根据引理$1$又可得完全图中两点的公共顶点恰好为完全图内的其他点。
设原图存在一个不在完全图中的点$w$，取一个包含完全图两点$a_1,a_2(a_1\ne a_2)$与$w$的点集，得到它的中间点为$x$，且$x$在完全图中。那么再取一个包含$a_1,x,w$的点集，可得另一个中间点为$y$，且$y$在完全图中，那么$x$与$y$存在公共顶点$w$，而因为完全图总两点的公共顶点为完全图内的其他点，因此$w$在完全图内，故不存在完全图外的点，即原图为一个$k+1$个点的完全图。
知道了该图为$k+1$个点的完全图，这道题就简单了。
我们考虑仅存在$n$个不同的子集，那么很显然对于每一个子集，该子集外的点便为这个子集的中间点，也就是说每个点都会作为中间点计算一次，我们直接算所有点连接的所有边边权之和除以$n$就好了。
时间复杂度：$O(n^2)$。
## 代码
```
#include<stdio.h>
#include<vector>
#define int long long
using namespace std;
const int maxn=2005;
int n,k,ans;
vector< pair<int,int> >v[maxn];
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
int x;
scanf("%lld",&x);
if(x==-1)
continue;
v[i].push_back(make_pair(j,x));
v[j].push_back(make_pair(i,x));
}
if(k==1){
for(int i=1;i<=n;i++)
ans+=v[i][0].second;
printf("%lld\n",ans/n);
return 0;
}
if(k==2){
for(int i=1;i<=n;i++){
int cnt=0,sum=0;
for(int j=0;j<v[i].size();j++)
cnt++,sum+=v[i][j].second;
ans+=(cnt-1)*sum;
}
printf("%lld\n",ans/(n*(n-1)/2));
return 0;
}
for(int i=1;i<=n;i++)
for(int j=0;j<v[i].size();j++)
ans+=v[i][j].second;
printf("%lld\n",ans/n);
return 0;
}
```