P7842 「PMOI-4」可怜的团主

TonyYin · 2021-08-24 09:18:05 · 题解

题意

给定一个 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，下面给出证明。

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

代码没有给出头文件和 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;
}