「PMOI-4」可怜的团主

Subtask 1

对于 20% 的数据 $n , m \leq 10$

直接搜索即可，没有太多的细节

期望得分：$20$

Subtask 2

数据保证为一棵树

这时，我们只需将叶子节点随机配对。随机配对并不能够保证覆盖所有的点，这时就需要我们进行调整

对于每次调整，我们只需要找到一个未被覆盖的点作为 root（细节：该点不为叶子节点且至少有两个子树，否则它一开始就能被覆盖到）

任意取它的两个子树，并从中分别挑选两条路径 $(u,v)$ $(u',v')$ 将其调整成 $(u,v')$ $(v,u')$。

画图可知，这时 $root$ 一定被覆盖到，故可知在不超过 $n$ 步内可以完成调整

结合算法 $1$ ，期望得分：$40$

Subtask 3

从 Subtask2 扩展到一般情况

我们找出图中的 dfs 树（不存在横插边），然后再结合算法2即可

期望得分：$100$

感谢 ducati 老师教会了我

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;

inline int read() { //速读 
	int f = 1 , ret = 0;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c <= '9' && c >= '0') {
		ret = (ret << 3) + (ret << 1) + c - 48;
		c = getchar();
	}
	return ret * f;
}

int cnt , Head[MAXN];

struct Edge {
	int Next , To;
}Edge[MAXN << 1]; 

void Add(int u , int v) {
	cnt++;
	Edge[cnt].To = v;
	Edge[cnt].Next = Head[u];
	Head[u] = cnt;
} //前向星存图 (20 ~ 31)

vector<int> G[MAXN] , res;

bool Vis[MAXN] , Covered[MAXN] , book[MAXN];
int Leaf[MAXN] , Deg[MAXN]; //存叶节点和每个点的度
int N , M , Len , Rest , Extra; 
int Pair[MAXN];
//Pair[i] = j表示把（i ， j）配成一对
//配对是互相的 

void Get_Dfs_Tree(int now) { //找dfs树 
	Vis[now] = true; //标记
	for(int i = 0;i < G[now].size();i++) { //vector存图 
		int v = G[now][i];
		if(!Vis[v]) {
			Get_Dfs_Tree(v);//以v为root的子树递归求解
			Deg[now]++;
			Deg[v]++; //更新两点的度
			Add(now , v);
			Add(v , now); //加入前向星 
		}
	} 
}

bool Dfs(int now , int dv , int father , int flag) {
	if(now == dv) {
		Covered[now] = true;
		if(flag == true && now != Extra) res.push_back(now);
		return true;
	}
	bool Val = false;
	for(int u = Head[now] ; u ; u = Edge[u].Next) {
		int v = Edge[u].To;
		if(v == father) continue;
		if(Dfs(v , dv , now , flag)) {
			Val = true;
			Covered[now] |= 1;
		}
	}
	if(flag == 1 && Val == 1 && now != Extra) res.push_back(now);//特判now ！= Extra 
	return Val;
}

int Get_Leaf(int now , int father) {
	if(Deg[now] == 1) return now; // 度为一的点——叶子 
	for(int u  = Head[now] ; u ; u = Edge[u].Next) {
		int v = Edge[u].To;
		if(v != father) return Get_Leaf(v , now); //递归子树 
	}
}

void Make_Pair(int u , int v) {
	Pair[u] = v;
	Pair[v] = u;
	//配对是互相的 
	Dfs(u , v, 0 , 0);
} 

void print(int u,int v){
	res.clear();
	Dfs(u , v , 0 , 1);
	Rest--;
	printf("%d ",res.size());
	for (int i = 0 ; i < res.size() ; i++){
		printf("%d ",res[i]);
	}
	puts("");
}

int main() {
	N = read();
	M = read();
	Rest = (N + 5) / 6;
	for(int i = 1;i <= M;i++) {
		int u = read();
		int v = read();
		G[u].push_back(v);
		G[v].push_back(u); //vector存图 
	}
	Get_Dfs_Tree(1); //将1作为根 
	for(int i = 2;i <= N;i++) { //细节：从i : 2 -> N ，因为1是根，可能存在1->叶子的边 
		if(Deg[i] == 1)
			Leaf[++Len] = i; //叶子节点集合 
	}
	if(Len >= N / 3) { //处理 b6e0 
		puts("2");
		for(int i = 1;i <= N / 3;i++) {
			cout << Leaf[i] << " ";
		}
		return 0;
	}
	if(Deg[1] == 1) Leaf[++Len] = 1;  //单独处理root 
	if(Len % 2 == 1) { // 若Len为奇数，那么我们连一条从 1 到 n+1 的边，增加一个叶节点，输出时特判 
		Add(1 , ++N);
		Deg[N] = 1;
		Leaf[++Len] = N;
		Extra = N; //特判时使用 
	}
	for(int i = 1;i <= Len;i += 2) { //为了方便，写124行 
		Make_Pair(Leaf[i] , Leaf[i + 1]); //配对 
	}
	while(true) {
		int now , Cnt_Son = 0 , u1 , v1 , u2 , v2 , done = 1;
		for(int i = 1;i <= N;i++) {
			if(!Covered[i]) {
				now = i;
				done = false;
				break;
			}
		}
		if(done) break;
		for(int i = Head[now] ; i ; i = Edge[i].Next) {
			int j = Edge[i].To;
			Cnt_Son++;
			if(Cnt_Son == 1) {
				u1 = Get_Leaf(j , now);
				v1 = Pair[u1]; 
			}
			else if(Cnt_Son == 2) {
				u2 = Get_Leaf(j , now);
				v2 = Pair[u2]; 
			}
			else break;
		}
		Make_Pair(u1 , v2);
		Make_Pair(v1 , u2);
	} 
	puts("1");
	for(int i = 1;i <= Len;i++) {
		int u = Leaf[i];
		int v = Pair[Leaf[i]];
		if(u < v) print(u , v);
	}
	for(int i = 1;i <= Rest;i++)
		cout << 1 << " " << i << endl; 
	return 0;
}