【LGR-088】洛谷 8 月月赛 & 「PMOI」Round · 04 ">【LGR-088】洛谷 8 月月赛 & 「PMOI」Round · 04 "> 洛谷 - P7842 -「PMOI-4」可怜的团主 - TonyYin
洛谷 – P7842 -「PMOI-4」可怜的团主

题意

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

  1. 找到恰好 $\lceil\frac{n}{6}\rceil$​​​ 条不同的路径,​使每个点都至少被一条路径经过。(每条路径上,每个点至多经过一次)
  2. 找到恰好 $\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;
    }
}

$\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);
}

操作一定可行的证明

对于一个没有被覆盖的点 $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;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇