【2021集训队出题】交朋友

by AmanoKumiko

Description

给出一个图，构造尽量少的团，使得团中边覆盖了整个图

Input

第一行两个数\(n,m\)，表示点数和边数

接下来\(m\)行，每行两个数\(x,y\)，表示一条边

Output

第一行一个数\(k\)，表示团的数量

接下来\(k\)行输出团

Sample Input

4 5
1 2
1 3
2 3
2 4
3 4

Sample Output

2
3 1 2 3
3 2 3 4

Data Constraint

\(n\le10^3\)

Solution

对于前两个点：手算

第三个点：由于给出的是二分图，所以团数就是边数

接下来开始动脑子了

1.我会暴力！（跑不动

2.我会随机！（分不多

3.一直贪心地找最大团！期望得分\(28\)

4.其它算法（估价函数、乱搞……）期望得分\(???\)

一种可行做法：

我们从始至终维护一个团的集合\(A\)，保证它们中的边覆盖了整个图

那么依次执行以下操作：

（1）对于每个团，考虑每个点，若不在团内且可加入就放进去

（2）对于每个团，尝试删去，若仍覆盖了图，就删去

（3）对于每个团，考虑团中每个点，尝试删去，若仍覆盖了图，就删去

可以发现，\(|A|\)是不上升的

为了保证能弄出解，对枚举顺序随机打乱以下

对所有测试点运行一段时间（2h）即可

Code

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define random(x) rand()%(x)
#define N 1010
#define M 1000010

int n,m,f[N][N],t[N][N],p[M],sz,x[M],y[M],vis[M],T,pnum[N];
vector<int>C[M],c[M];

int main(){
	freopen("friends10.in","r",stdin);
	scanf("%d%d",&n,&m);
	F(i,1,m){
		scanf("%d%d",&x[i],&y[i]);
		f[x[i]][y[i]]=f[y[i]][x[i]]=1;
		t[x[i]][y[i]]++;t[y[i]][x[i]]++;
		C[i].push_back(x[i]);
		C[i].push_back(y[i]);
	}
	sz=m;
	srand(time(0));
	F(i,1,n)p[i]=i;
	int lst=sz;
	while(sz>8486){
		srand(time(0));
		srand(rand());
		random_shuffle(p+1,p+n+1);
		F(j,1,sz) F(i,1,n){
			bool flag=1;
			for(auto px:C[j]){
				if(!f[px][p[i]]||px==p[i]){flag=0;break;}
			}
			if(flag){
				for(auto px:C[j]){
					t[px][p[i]]++;t[p[i]][px]++;
				}
				C[j].push_back(p[i]);
			}
		}
		random_shuffle(C+1,C+sz+1);
		F(i,1,sz)vis[i]=0;
		F(i,1,sz){
			bool flag=1;
			for(auto px:C[i]){
				for(auto py:C[i]){
					if(px==py)continue;
					t[px][py]--;
					if(t[px][py]<1)flag=0;
				}
			}
			if(flag)vis[i]=1;
			else{
				for(auto px:C[i]){
					for(auto py:C[i]){
						if(px==py)continue;
						t[px][py]++;
					}
				}
			}
		}
		F(j,1,sz)if(!vis[j]){
			random_shuffle(C[j].begin(),C[j].end());
			F(i,0,C[j].size()-1){
				bool flag=1;
				for(auto px:C[j]){
					if(px==C[j][i])continue;
					t[px][C[j][i]]--;t[C[j][i]][px]--;
					if(t[px][C[j][i]]<1||t[C[j][i]][px]<1)flag=0;
				}
				if(flag){
					swap(C[j][i],C[j][C[j].size()-1]);
					C[j].pop_back();
				}
				else{
					for(auto px:C[j]){
						if(px==C[j][i])continue;
						t[px][C[j][i]]++;t[C[j][i]][px]++;
					}
				}
				if(C[j].size()<1)vis[p[j]]=1;
			}
		}
		int tail=0;
		F(i,1,sz)if(!vis[i])c[++tail]=C[i];
		sz=tail;
		F(i,1,sz)swap(C[i],c[i]);
		if(sz<lst)printf("%d\n",sz);
		lst=sz;
	}
	freopen("friends10.out","w",stdout);
	printf("%d\n",sz);
	F(i,1,sz){
		printf("%d ",C[i].size());
		for(auto px:C[i])printf("%d ",px);
		printf("\n");
	}
	return 0;
}