自动搬运

查看原文

来自洛谷，原作者为

	interestingLSY 4e6db374ed2fb0e68073d5d05c3b136e(md5)

搬运于2025-08-24 21:57:44，当前版本为作者最后更新于2018-08-14 12:11:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这题出的，emmmmmmmmmmm..............

首先介绍一类问题：最大团问题

“团”就是指从一个图中选出来一堆点，每对点间都直接有边相连。“最大团”就是指包含的点最多的那个团。这题就是个“最大团问题”

但不幸的是，最大团问题是NPC的。

目前最快的正确解法是状压dp......复杂度为$O(n^22^n)$,这题中 $n=50$ 显然会凉凉

怎么办。。。我们先暴搜一波......

int n;
bool gay[MAXN][MAXN];
int gaycnt[MAXN];

bool sel[MAXN];
il bool Cansel( int pos , int upp , int selcnt ){
	if( gaycnt[pos] < selcnt ) return 0;
	For(i,upp)
		if(sel[i]&&!gay[i][pos])
			return 0;
	return 1;
}
int ans = 0;
void Dfs( int pos , int tans , int cnt ){
	if( pos == n+1 ){
		Mymax(ans,tans);
		return;
	}
	if( tans + n-pos+1 <= ans ) return;
	int pmax = tans;
	Forx(i,pos,n)
		pmax += (int)Cansel(i,pos-1,cnt);
	if( pmax <= ans ) return;
	sel[pos] = 0;
	Dfs(pos+1,tans,cnt);
	if( Cansel(pos,pos-1,cnt) ){
		sel[pos] = 1;
		Dfs(pos+1,tans+1,cnt+1);
		sel[pos] = 0;
	}
}

好。70分。(楼下dalao各种剪枝90分%%%%%%)

然后。。点开分类标签，"乱搞"?emmmmmmmmm........

打不了表，考虑随机。

随机生成一个数列，并从前往后选。

WTF？AC了！

#define MAXN 60

int n;
bool gay[MAXN][MAXN];
int gaycnt[MAXN];
int u[MAXN];
int s[MAXN], top;

int ans = 0;
bool Check( int pos ){
	int v = ::u[pos];
	if( gaycnt[v] < top ) return 0;
	For(i,top){
		if(!gay[s[i]][v])
			return 0;
	}
	return 1;
}

int main(){
	Ms(gay);
	
	scanf("%d",&n);
	int a,b;
	while( scanf("%d%d",&a,&b) != EOF ){
		gay[a][b] = gay[b][a] = 1;
		gaycnt[a]++;
		gaycnt[b]++;
	}
	For(i,n)
		u[i] = i;
	
	srand((ull)new char);
	For(i,100000){
		top = 0;
		random_shuffle(u+1,u+1+n);
		int tans = 0;
		For(i,n){
			if(Check(i)){
				s[++top] = u[i];
				tans++;
			}
		}
		Mymax(ans,tans);
		if( ans == n ) break;
	}
	printf("%d\n",ans);
	
	return 0;
}