自动搬运

查看原文

来自洛谷，原作者为

	FZzzz **

搬运于2025-08-24 22:22:02，当前版本为作者最后更新于2020-05-27 17:51:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

翻译者来水个题解。

首先我之前把一句话题意翻错了，翻成了：

给一个图，每个点的度数不超过 $k$，求最大团。

先考虑这个东西咋做。

不是随便暴力吗。

就很显然地，钦定最大团里的某个点，然后在所有和它相连的点里枚举子集，判断是否可行，复杂度 $O(nk^22^k)$ 过了我请你吃糖。

我们预处理出一个点与哪些点连边，压位处理，这样就 $O(nk2^k)$ 了。

然后考虑原问题，我们想要把它转化成上面这个问题。

可以发现上面这个算法是很浪费的，因为一个子集被算了很多次。我们换个思路，可以枚举最大团里最小的节点，然后在它连向的后面的所有点里枚举子集。

问题是这样还是不能保证边数。可以考虑根据人类智慧构造一个排列，然后按上面的方法搞。

考虑到这个导出子图的度数限制，我们可以想到 dfs 处理，每次 dfs 到一个点就把它所有邻居的 $d$ 值减一，然后如果小于 $k$ 就访问它。

下面证明这个算法一定能得到一个结果：

根据算法可知，如果不能得到一个结果，那么一定是在把所有能访问的点都访问完之后，剩下的点的 $d$ 值全都不小于 $k$。那么这些点的生成子图不满足题中的性质，矛盾。于是命题得证。

然后有了这个我们就可以像上面一样暴力了，时间复杂度 $O(nk2^k)$。

#include<algorithm>
#include<vector>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-'){
		f=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=5e4+5;
int n,k,d[maxn];
vector<int> g[maxn],g2[maxn];
int pos[maxn],cnt=0;
bool vis[maxn];
void dfs(int u){
	vis[u]=1;
	pos[u]=cnt++;
	for(int i=0;i<(int)g[u].size();i++){
		int v=g[u][i];
		d[v]--;
		if(d[v]<k&&!vis[v]) dfs(v);
	}
}
bool beside(int u,int v){
	for(int i=0;i<(int)g2[u].size();i++)
		if(g2[u][i]==v) return 1;
	for(int i=0;i<(int)g2[v].size();i++)
		if(g2[v][i]==u) return 1;
	return 0;
}
int g3[maxn];
int calc(int u){
	for(int i=0;i<(int)g2[u].size();i++) g3[g2[u][i]]=0;
	for(int i=0;i<(int)g2[u].size();i++)
		for(int j=0;j<(int)g2[u].size();j++)
			if(i==j) g3[i]|=1<<j;
			else g3[i]|=beside(g2[u][i],g2[u][j])<<j;
	int ans=0;
	for(int i=0;i<(1<<g2[u].size());i++){
		int res=i,cnt=0;
		for(int j=0;j<(int)g2[u].size();j++) if(i>>j&1){
			res&=g3[j];
			cnt++;
		}
		if(res==i) ans=max(ans,cnt);
	}
	return ans+1;
}
int main(){
	#ifdef LOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	n=readint();
	k=readint();
	for(int i=0;i<n;i++){
		d[i]=readint();
		for(int j=0;j<d[i];j++) g[i].push_back(readint());
	}
	for(int i=0;i<n;i++) if(d[i]<k&&!vis[i]) dfs(i);
	for(int i=0;i<n;i++) for(int j=0;j<(int)g[i].size();j++)
		if(pos[g[i][j]]>pos[i]) g2[i].push_back(g[i][j]);
	int ans=0;
	for(int i=0;i<n;i++) ans=max(ans,calc(i));
	printf("%d\n",ans);
	return 0;
}