BZOJ2530 : [Poi2011]Party

时间:2024-01-15 23:28:26

注意到随机一组贪心解得到的团的大小不小于$\frac{N}{3}$的概率是很大的,所以一直随机下去,直到找到一组解即可,随机次数是常数级别的,所以复杂度为$O(n^2)$。

#include<cstdio>
#include<cstdlib>
#define N 3010
int n,m,i,j,k,a[N],del[N],fin[N];bool g[N][N];
inline void swap(int&a,int&b){int c=a;a=b;b=c;}
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
read(n),read(m);
while(m--)read(i),read(j),g[i-1][j-1]=g[j-1][i-1]=1;
for(i=0;i<n;i++)a[i]=i;
while(1){
for(i=0;i<n;i++)swap(a[i],a[std::rand()%n]);
for(i=0;i<n;i++)del[i]=0;
for(k=i=0;i<n;i++)if(!del[i])for(k++,j=i+1;j<n;j++)if(!g[a[i]][a[j]])del[j]=1;
if(k>=n/3){
for(i=j=0;i<n;i++)if(!del[i])fin[j++]=a[i];
for(i=0;i<n/3;i++)printf("%d ",fin[i]+1);
return 0;
}
}
}