每条边必须恰好有一个端点被选，因此图必须二分染色；每个连通块取两种颜色中较少的一侧。
OJ: luogu
题目 ID: P1330
难度:普及+/提高
标签:图论二分图染色bfs
日期: 2026-06-19 19:29
题意
给出一张无向图。要选出若干个点去封锁，使得：
- 每条边至少有一个端点被封锁
- 任意两个相邻点不能同时被封锁
要求封锁点数量最少；若做不到，输出 Impossible。
思路
最直接的办法是暴力枚举选哪些点。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u;
int v;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<Edge> edges(m);
for (int i = 0; i < m; ++i) {
cin >> edges[i].u >> edges[i].v;
}
int best = INT_MAX;
for (int mask = 0; mask < (1 << n); ++mask) {
bool ok = true;
int cnt = __builtin_popcount((unsigned)mask);
for (const auto &e : edges) {
bool pick_u = (mask >> (e.u - 1)) & 1;
bool pick_v = (mask >> (e.v - 1)) & 1;
if (!pick_u && !pick_v) {
ok = false;
break;
}
if (pick_u && pick_v) {
ok = false;
break;
}
}
if (ok) {
best = min(best, cnt);
}
}
if (best == INT_MAX) {
cout << "Impossible\n";
} else {
cout << best << '\n';
}
return 0;
}下面是另一种「01 序列」风格的暴力写法。它按点编号依次决定“封锁 / 不封锁”，递归生成完整选择后，叶子节点统一检查每条边是否恰好有一个端点被选，并统计最少封锁点数：
另一种暴力写法：01 序列
cpp
// brute_01_style.cpp：01 序列风格暴力，按点编号依次决定选或不选。
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u;
int v;
};
const int MAXN = 25;
int n, m;
vector<Edge> edges;
int chosen[MAXN]; // chosen[i] 表示第 i 个点是否被封锁。
int best;
bool check() {
for (int i = 0; i < (int)edges.size(); i++) {
int u = edges[i].u;
int v = edges[i].v;
// 每条边必须恰好有一个端点被选。
if (chosen[u] == chosen[v]) {
return false;
}
}
return true;
}
int calc_answer() {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (chosen[i] == 1) cnt++;
}
return cnt;
}
void dfs_choose(int dep) {
if (dep == n + 1) {
if (check()) {
int value = calc_answer();
if (best > value) best = value;
}
return;
}
// 第 dep 个点的 01 选择：0 不封锁，1 封锁。
for (int i = 0; i <= 1; i++) {
chosen[dep] = i;
dfs_choose(dep + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
edges.resize(m);
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v;
}
best = n + 1;
dfs_choose(1);
if (best == n + 1) {
cout << "Impossible\n";
} else {
cout << best << '\n';
}
return 0;
}brute.cpp 直接检查每条边是否满足“恰好选一个端点”，适合小图对拍。
真正的关键是：对任意一条边 (u, v)，
- 如果两个端点都不选，这条边没被封锁
- 如果两个端点都选，会发生冲突
所以每条边必须恰好选一个端点。
这张图对比了两种典型情况：
graph G {
subgraph cluster_ok {
label="链";
a1 -- a2;
a2 -- a3;
}
subgraph cluster_bad {
label="奇环";
b1 -- b2;
b2 -- b3;
b3 -- b1;
}
}
从图中可以看到，链可以二分成两侧，任选一侧就能覆盖所有边；而奇环没法做到“每条边恰好跨越选与不选”，所以直接无解。
因此做法就是：
- 对每个连通块做二分图染色
- 若遇到相邻同色，输出
Impossible - 否则这个块只能整块选某一种颜色，答案加上
min(cnt0, cnt1)
代码
cpp
#include <bits/stdc++.h>
using namespace std;
static vector<vector<int>> g;
static vector<int> color;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
g.assign(n + 1, {});
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
color.assign(n + 1, -1);
int ans = 0;
for (int s = 1; s <= n; ++s) {
if (color[s] != -1) {
continue;
}
queue<int> q;
q.push(s);
color[s] = 0;
int cnt[2] = {1, 0};
bool ok = true;
while (!q.empty() && ok) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1;
++cnt[color[v]];
q.push(v);
} else if (color[v] == color[u]) {
ok = false;
break;
}
}
}
if (!ok) {
cout << "Impossible\n";
return 0;
}
ans += min(cnt[0], cnt[1]);
}
cout << ans << '\n';
return 0;
}复杂度
整张图只做一次 BFS 染色，所以时间复杂度是
总结
这题的关键是把“覆盖所有边且选中点之间不能相邻”翻译成“每条边恰好选一个端点”。一旦看出这一点，问题就直接变成二分图染色。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
