【洛谷-P7842】「PMOI-4」可怜的团主

题意#

给定一个 $n$ 个点， $m$ 条边的简单连通无向图，问：是否能实现以下两个操作中的一个：

找到恰好 $\lceil\frac{n}{6}\rceil$ 条不同的路径，使每个点都至少被一条路径经过。（每条路径上，每个点至多经过一次）
找到恰好 $\lfloor\frac{n}{3}\rfloor$ 个点，使其中两两没有边。

若能实现操作1，输出每条路径；若能实现操作2，输出满足条件的这些点。

对于 $100\%$ 的数据， $3\leq n\leq 10^3$ ， $3\leq m\leq \dfrac{n(n-1)}{2}$ .

$\rm{Subtask}$ $1$ #

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

暴力搜索即可。期望得分 20 分。

for(int sta = 0; sta < (1 << n); sta++) {
    int cnt = 0; bool wrong = false;
    for(int i = 1; i <= n; i++) {
        if(sta & (1 << (i - 1))) cnt++;
    }
    if(cnt != n / 3) continue;
    for(int i = 1; i <= n; i++) if(sta & (1 << (i - 1))) {
        for(int j = 1; j <= n; j++) if(sta & (1 << (j - 1))) {
            if(i == j) continue;
            if(mapp[i][j]) {wrong = true; break;}
        }
        if(wrong) break;
    }
    if(!wrong) {
        cout << 2 << endl;
        for(int i = 1; i <= n; i++) {
            if(sta & (1 << (i - 1))) cout << i << " ";
        } cout << endl;
        return 0;
    }
}

cpp

$\rm{Subtask}$ $2$ #

对于另外 $20\%$ 的数据，图是一棵树。

算法一#

将树上的点按深度奇偶性分类，然后选择这两类中较大的那一个作为独立集。

显然这个独立集大小大于 $n/2$ ，满足要求。

很好写，就不给代码了。

算法二#

考虑满足操作二的构造方法，这更接近正解。

任意找一个点为根，找出所有 $x$ 个叶子。

如果 $x\leq \lfloor\frac{n}{3}\rfloor$ ，那么满足操作一。

否则，构造出一些以这些叶子为两端的路径，使得这些路径覆盖到图上所有的点。

可以证明，这样的路径一定存在，并且最小覆盖数是 $\lceil\frac{x}{2}\rceil$ . 下面给出可行的构造方法，即可证明。

构造方案#

首先，将叶子任意两两配对。若 $x$ 为奇数，那么加一个点编号为 $n+1$ ，直接连在根节点 $1$ 下面。

显然配对不一定能覆盖所有的点，所以考虑进行若干次调整。

对于每次调整，我们找到一个没有被覆盖的点 $p$ ，之后找 $p$ 的任意两个子树，从这两个子树中分别找到任意两个叶子，记为 $(u, v)$ ， $(u', v')$ .

直接把这两条路径变换一下配对顺序，变为 $(u, v')$ 和 $(v, u')$ . 这样一定可以使 $p$ 被覆盖到，至少多覆盖了一个点。

由于每次操作，都会多覆盖 $\geq 1$ 个点，所以最多进行 $n$ 次，时间复杂度为 $\mathcal{O}(n^2)$ ，可以接受。

可以证明操作四个点一定能找到，操作一定可行。

for(int i = 1; i <= n; i++) if(!covered[i]) {
    int son_cnt = 0, leaf1, leaf2, leaf3, leaf4;
    for(int j = head[i]; j; j = edge[j].nxt) {
        int v = edge[j].to;
        son_cnt++;
        if(son_cnt == 1) {
            leaf1 = Get_leaf(v);
            leaf2 = Pair[leaf1];
        } else if(son_cnt == 2) {
            leaf3 = Get_leaf(v);
            leaf4 = Pair[leaf3];
            break;
        }
    }
    Make_pair(leaf1, leaf3); Make_pair(leaf2, leaf4);
}

cpp

操作一定可行的证明#

对于一个没有被覆盖的点 $p$ ，其每个子树内叶子个数一定 $\geq 2$ ，下面给出证明。

由于没有被覆盖，所以子树内的每条路径，都仅在儿子的子树内，如下图：

例 - 图.jpeg

$\rm{y}$ 存在一棵子树仅有一个叶子。红色节点相关的路径，必定会覆盖到 $\rm{y}$ .

$\rm{x}$ 是一种不被覆盖的可行情况。

$\rm{Subtask}$ $3$ #

容易想到，在无向图中找一棵生成树，尝试继续使用上面的方法进行构造。

注意到， $\rm{Subtask}$ $2$ 中，利用了树的重要性质：叶子之间没有边。

因此，我们在原图上找到DFS树。这样能满足叶子节点之间，在原图上没有边。

使用 $\rm{Subtask}$ $2$ 的算法二解决即可。

$\rm{Code}$ #

代码没有给出头文件和 read() 函数。

dfs1(int)，dfs2(int, int)，get_lca(int, int) 实现了树剖LCA。

由于本题时间复杂度为 $\mathcal{O}(n^2)$ ，可以不用这种方法求 LCA，暴力找 LCA 也可以通过。

代码细节较多）

using namespace std;
const int MAXN = 1e3 + 10, MAXM = 2e6 + 10;

int n, m, extra;
vector<int> mp[MAXN];
struct Edge{
	int from, to, nxt;
} edge[MAXM];
int head[MAXN], e_cnt = 0;
void add_edge(int u, int v) {
	edge[++e_cnt] = (Edge){u, v, head[u]};
	head[u] = e_cnt;
}
int vis[MAXN], dep[MAXN], fa[MAXN], deg[MAXN];
void Get_DFS_Tree(int u, int father) {
	vis[u] = true;
	dep[u] = dep[father] + 1; fa[u] = father;
	for(int i = 0; i < mp[u].size(); i++) {
		int v = mp[u][i]; if(vis[v]) continue;
		Get_DFS_Tree(v, u);
		deg[u]++; deg[v]++;
		add_edge(u, v); add_edge(v, u);
	}
}
int siz[MAXN], son[MAXN], dfn[MAXN], top[MAXN], tot;
void dfs1(int u) {
	siz[u] = 1;
	for(int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to; if(v == fa[u]) continue;
		dfs1(v);
		if(!son[u] || siz[v] > siz[son[u]]) son[u] = v;
		siz[u] += siz[v];
	}
}
void dfs2(int u, int topf) {
	top[u] = topf; dfn[u] = ++tot;
	if(!son[u]) return;
	dfs2(son[u], topf);
	for(int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to; if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}
int get_lca(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	if(dep[u] < dep[v]) swap(u, v);
	return v;
}
int leaf[MAXN], leaf_cnt;
int Pair[MAXN], covered[MAXN];
void Cover(int x, int y) {
	if(x == y) {covered[x] = 1; return;}
	do{
		covered[x] = covered[y] = 1;
		if(dep[x] > dep[y]) x = fa[x];
		else y = fa[y];
	} while(x != y);
}
void Make_pair(int x, int y) {
	Pair[x] = y; Pair[y] = x;
	Cover(x, y);
}
int Get_leaf(int u) {
	while(deg[u] != 1) {
		for(int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to; if(v != fa[u]) {u = v; break;}
		}
	}
	return u;
}
void print_path(int u, int v) {
	if(u == extra) u = fa[u];
	if(v == extra) v = fa[v];
	int lca = get_lca(u, v);
	vector<int> p1, p2;
	int x = u; while(x != lca) {p1.push_back(x); x = fa[x];}
	x = v; while(x != lca) {p2.push_back(x); x = fa[x];}
	printf("%d ", p1.size() + p2.size() + 1);
	for(int i = 0; i < p1.size(); i++) printf("%d ", p1[i]);
	printf("%d ", lca);
	for(int i = p2.size() - 1; i >= 0; i--) printf("%d ", p2[i]);
	putchar('\n');
}
int main() {
	srand(time(0));
	n = read(); m = read();
	int rest = (n + 5) / 6;
	for(int i = 1; i <= m; i++) {
		int u = read(), v = read();
		mp[u].push_back(v); mp[v].push_back(u);
	}
	Get_DFS_Tree(1, 0);
	dfs1(1); dfs2(1, 1);
	for(int i = 2; i <= n; i++) if(deg[i] == 1) leaf[++leaf_cnt] = i;
	if(leaf_cnt >= n / 3) {
		putchar('2'); putchar('\n');
		for(int i = 1; i <= n / 3; i++) printf("%d ", leaf[i]);
		return 0;
	}
	if(deg[1] == 1) leaf[++leaf_cnt] = 1;
	if(leaf_cnt & 1) {
		n++; fa[n] = 1; deg[n] = 1; leaf[++leaf_cnt] = n;
		extra = n;
		add_edge(1, n); add_edge(n, 1);
	}
	for(int i = 2; i <= leaf_cnt - 1; i += 2) Make_pair(leaf[i], leaf[i + 1]);
	Make_pair(leaf[1], leaf[leaf_cnt]);
	for(int i = 1; i <= n; i++) if(!covered[i]) {
		int son_cnt = 0, leaf1, leaf2, leaf3, leaf4;
		for(int j = head[i]; j; j = edge[j].nxt) {
			int v = edge[j].to;
			son_cnt++;
			if(son_cnt == 1) {
				leaf1 = Get_leaf(v);
				leaf2 = Pair[leaf1];
			} else if(son_cnt == 2) {
				leaf3 = Get_leaf(v);
				leaf4 = Pair[leaf3];
				break;
			}
		}
		Make_pair(leaf1, leaf3); Make_pair(leaf2, leaf4);
	}
	putchar('1'); putchar('\n');
	for(int i = 1; i <= leaf_cnt; i++) {
		int u = leaf[i], v = Pair[leaf[i]];
		if(u > v) continue; //保证每条路径只被输出一次
		print_path(u, v); rest--;
	}
	for(int i = 1; i <= rest; i++) {
		print_path(rand() % n + 1, i);//这个我也不清楚咋解决
	}
	return 0;
}

cpp

题意#

Subtask\rm{Subtask}Subtask​ 111​#

Subtask\rm{Subtask}Subtask 222#