[POI 2010] GIL-Guilds

GitHub跳转原题关系图返回列表

先判图中是否有孤立点；若没有，就对每个连通块的生成树二染色，直接构造两个互不重叠的覆盖方案。

OJ: luogu

题目 ID: P3496

难度:普及+/提高

标签:图论构造bfs思维

日期: 2026-06-20 14:46

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给一个无向图，每个点代表一个城镇。

要给两个行会安排办事处，要求：

  1. 一个城镇不能同时设两个行会的办事处
  2. 对任意一个行会来说，每个城镇都必须：
    • 要么自己就设了这个行会的办事处
    • 要么与一个设了这个行会办事处的城镇直接相连

如果可以，输出 TAK 和一种可行方案；否则输出 NIE。

思路

这题虽然表面上像“两个支配集”的构造题，但关键观察非常短。

先看代码里采用的直接构造版本：

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

const int MAXN = 35;

int n, m;
vector<int> g[MAXN];
int deg_arr[MAXN];
int color_arr[MAXN];

// brute.cpp：这里保留最直接的构造版写法。
// 这题的关键结论本身就很简单：
// 只要没有孤立点，就一定可以构造。
// 因此这个文件不再去枚举 3^n 的所有方案，而是直接按生成树二染色实现。

void bfs_component(int start) {
    queue<int> q;
    color_arr[start] = 1;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (color_arr[v] == 0) {
                color_arr[v] = 3 - color_arr[u];
                q.push(v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        deg_arr[i] = 0;
        color_arr[i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg_arr[u]++;
        deg_arr[v]++;
    }

    for (int i = 1; i <= n; i++) {
        if (deg_arr[i] == 0) {
            cout << "NIE\n";
            return 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (color_arr[i] == 0) {
            bfs_component(i);
        }
    }

    cout << "TAK\n";
    for (int i = 1; i <= n; i++) {
        if (color_arr[i] == 1) {
            cout << "K\n";
        }
        else {
            cout << "S\n";
        }
    }

    return 0;
}

先想无解情况。

如果图里有一个孤立点，那么它没有任何邻居。

这时无论你把它设成 K、S 还是 N，总会有至少一个行会无法覆盖它，所以一定无解。

再想有解情况。

如果图里没有孤立点，那么对每个连通块取一棵生成树，在树上做二染色：

  • 根染成 K
  • 儿子染成 S
  • 再下一层染回 K

这样每个点都会满足两件事：

  1. 它自己属于某一种颜色，所以对应那个行会时，自己就已经被覆盖
  2. 在生成树里，它一定至少有一个相邻点颜色和自己相反：
    • 非根点有父亲
    • 根点由于不是孤立点，至少有一个儿子

所以另一个行会也一定能通过这个异色邻点覆盖到它。

于是可以得到整题结论：

  • 有孤立点，当且仅当无解
  • 没有孤立点，就一定有解

题目允许输出 N，但其实完全不需要。 我们直接把所有点都染成 K/S 两种颜色，就已经足够构造出合法方案。

代码

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

const int MAXN = 200005;

int n, m;
vector<int> g[MAXN];
int deg_arr[MAXN];
int color_arr[MAXN]; // 0: 未染色, 1: K, 2: S

void bfs_component(int start) {
    queue<int> q;
    color_arr[start] = 1; // 每个连通块根节点固定染成 K
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (color_arr[v] == 0) {
                color_arr[v] = 3 - color_arr[u];
                q.push(v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        deg_arr[i] = 0;
        color_arr[i] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg_arr[u]++;
        deg_arr[v]++;
    }

    // 只要存在孤立点，就一定无解。
    // 因为这个点无论是否给其中一个行会设办事处，
    // 另一个行会都无法通过相邻城镇来覆盖它。
    for (int i = 1; i <= n; i++) {
        if (deg_arr[i] == 0) {
            cout << "NIE\n";
            return 0;
        }
    }

    // 对每个连通块取一棵生成树，然后二染色。
    // 每个点都会至少有一个生成树中的相邻点颜色与自己相反，
    // 再加上它自己所在的颜色，就能同时被两个行会覆盖。
    for (int i = 1; i <= n; i++) {
        if (color_arr[i] == 0) {
            bfs_component(i);
        }
    }

    cout << "TAK\n";
    for (int i = 1; i <= n; i++) {
        if (color_arr[i] == 1) {
            cout << "K\n";
        }
        else {
            cout << "S\n";
        }
    }

    return 0;
}

复杂度

  • 时间复杂度：O(n+m)O(n + m)
  • 空间复杂度：O(n+m)O(n + m)

总结

这题最核心的不是复杂数据结构，而是把问题看穿：

  1. 孤立点一定无解
  2. 没有孤立点时，生成树二染色就能保证每个点都有异色邻居

一旦抓住这个结论，题目基本就变成一道非常直接的图构造题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析