关押罪犯(贪心+二分答案+染色法判定二分图/扩展域并查集)
题目描述
S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1∼N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式
每行中两个数之间用一个空格隔开。第一行为两个正整数 N,M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 M 行每行为三个正整数 aj,bj,cj，表示 aj 号和 bj 号罪犯之间存在仇恨，其怨气值为 cj。数据保证 1<aj<bj≤N,0<cj≤109，且每对罪犯组合只出现一次。
输出格式
共一行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。
分析:
第一种方法:
使用并查集:
变量含义介绍
N: 定义了节点数的上限，这里设置为 20010，表示最多有 20010 个节点。
p[N]: 并查集的父数组，用于记录每个节点的父节点，实现路径压缩优化。
e 结构体：
u, v: 边的两个顶点。
w: 边的权值。
重载 < 运算符，使得结构体按权值 w 从大到小排序。
a[N*5]: 存储所有边的数组，最多可容纳 5*N 条边，满足题目中可能的边数范围。
enemy[N]: 记录每个节点的一个敌对节点。例如，enemy[u] = v 表示 u 和 v 是敌人。
read() 函数：快速读取整数，避免 cin 的缓慢输入。
find(int x): 并查集的查找函数，返回节点 x 的根节点，并进行路径压缩。
merge(int x, int y): 合并节点 x 和 y 所在的集合。
n, m: 输入的节点数和边数。
贪心策略与排序
将边按权值从大到小排序，优先处理权值大的边。这样，当第一次出现冲突（两个敌人在同一集合）时，当前边的权值即为答案，保证了答案的最小性。
并查集与敌人关系处理
处理边 (u, v) 时，若 u 已有敌人 enemy[u]，则将 enemy[u] 与 v 合并；同理处理 v 的敌人。
这一步的核心逻辑是：敌人的敌人是朋友。通过合并敌人的敌人，尽可能避免同一集合中出现直接敌人。
代码流程
输入数据并存储到数组 a。
初始化并查集，按权值降序排序边。
遍历每条边，检查是否冲突：
若冲突，输出当前边的权值并结束。
否则，处理敌人关系，合并相关节点。
若无冲突，输出 0。
正确性证明
贪心正确性：按权值降序处理边，确保首次冲突时的边权是最小可能的答案。
合并逻辑正确性：通过合并敌人的敌人，保证同一集合内的节点不存在直接敌对关系。若最终仍出现冲突，则说明无法避免，当前边的权值即为答案。
代码:
#include <bits/stdc++.h>using namespace std;
const int N = 20010;int p[N];
typedef struct e {
int u, v, w;
bool operator < (const e& a) {
return w > a.w;
}
} e;
e a[N*5];int enemy[N];
// 快速读入整数的函数inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
// 查找元素所在集合的根节点inline int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
// 合并两个元素所在的集合inline void merge(int x, int y) {
int px = find(x), py = find(y);
if (px != py) p[px] = py;
}
int n, m;
int main() {
// 使用快读读取 n 和 m
n = read();
m = read();
for (int i = 0; i < m; i++) {
// 使用快读读取每条边的信息
int u = read();
int v = read();
int w = read();
a[i] = {u, v, w};
}
// 初始化并查集
for (int i = 1; i <= n; i++) p[i] = i;
// 按边权从大到小排序
sort(a, a + m);
// 遍历每条边
for (int i = 0; i < m; i++) {
int u = a[i].u;
int fu = find(u);
int v = a[i].v;
int fv = find(v);
// 如果两个端点已经在同一集合中，输出当前边的边权并结束程序
if (fu == fv) {
printf("%d\n", a[i].w);
return 0;
}
// 处理敌对关系
if (!enemy[u]) enemy[u] = v;
else merge(enemy[u], v);
if (!enemy[v]) enemy[v] = u;
else merge(enemy[v], u);
}
// 若所有边都处理完仍未找到符合条件的边，输出 0
cout << 0 << endl;
return 0;
}
方法二:二分答案+染色法判定二分图
分析:
1. 问题核心
给定带权无向图，寻找最大权值 mid，使得仅保留权值 > mid 的边时，图是二分图。
2. 二分查找的应用
目标：在权值范围 [0, 1e9] 内寻找最大 mid。
逻辑：
性质：若 mid 可行（对应子图是二分图），则所有小于 mid 的值也可行。
二分策略：
初始范围 l=0, r=1e9。
计算中间值 mid = (l + r + 1) / 2（避免死循环）。
检查 mid 是否可行：
可行 → 尝试更大的 mid（l = mid）。
不可行 → 缩小范围（r = mid - 1）。
3. DFS 验证二分图
目标：判断权值 > mid 的子图是否为二分图。
关键逻辑：
颜色标记：用 color 数组记录节点颜色（1/2）。
DFS 遍历：
对每个未染色的节点，尝试染色。
遍历其邻接边，若边权 ≤ mid → 跳过。
若邻接节点已染色且颜色相同 → 非二分图。
若未染色 → 递归染色为相反颜色。
正确性：DFS 确保连通子图的二分性，遍历所有节点确保全局二分性。
4. 正确性证明
二分查找正确性：
单调性：若 mid 可行，则所有更小值也可行，因此二分可找到最大值。
DFS 验证正确性：
二分图定义：相邻节点颜色不同。DFS 通过递归强制相邻节点颜色不同，若冲突则非二分图。
5. 复杂度分析
时间：
二分查找：O(log(1e9)) ≈ 30 次。
每次验证：O(n + m)（DFS 遍历所有节点和边）。
总复杂度：O(30(n + m))。
空间：
邻接表存储边：O(m)。
颜色数组：O(n)。
6. 关键细节
避免死循环：
计算 mid 时加 1（mid = (l + r + 1) / 2），确保 l < r 时 mid 正确递增。
颜色数组重置：
每次验证前需重置 color 数组为 0（未染色）。
处理孤立节点：
未染色的节点需单独启动 DFS，确保所有连通分量均为二分图。
7. 常见错误点
边权判断错误：误将 mid ≥ w 作为跳过条件（应 mid ≥ w 时跳过，即保留 w > mid 的边）。
颜色冲突处理：发现颜色相同节点时需立即返回 false，而非跳过。
二分边界处理：初始 r 设为 1e9 需覆盖所有可能权值，避免遗漏。
8. 总结
方法核心：利用二分查找的单调性快速缩小范围，结合 DFS 验证每个候选值的可行性。
优势：高效解决带权二分图问题，时间复杂度可控。
适用场景：类似 “最大 / 最小满足条件的阈值” 问题，且条件可通过二分图验证。
代码:
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define x first
#define y second
typedef pair<int, int> pii;
const int N = 20010;
int n, m;
unordered_map<int, vector<pii>> e;
bool color[N];
// 深度优先搜索函数，判断从节点 u 开始，在权值大于等于 mid 的边构成的子图中是否能进行二分染色
bool dfs(int col, int u, int mid) {
color[u] = col;
for (pii t : e[u]) {
int v = t.x;
int w = t.y;
if (mid > w) continue;
if (color[v]) {
if (color[v] == color[u]) return false;
} else {
if (!dfs(3 - col, v, mid)) return false;
}
}
return true;
}
// 检查在给定权值 mid 下，整个图是否能构成二分图
bool check(int mid) {
memset(color, 0, sizeof color);
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!dfs(1, i, mid)) return false;
}
}
return true;
}
int main() {
// 统一使用 scanf 进行输入
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
e[u].push_back({v, w});
e[v].push_back({u, w});
}
int l = 0, r = 1e9;
while (l < r) {
// 避免二分查找死循环，mid 向上取整
int mid = (l + r + 1) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
// 输出最终结果
cout << l << endl;
return 0;
}
棋盘覆盖(棋盘二分图+最大匹配);
给定一个 NN 行 NN 列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为 22、宽度为 11 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
输入格式
第一行包含两个整数 NN 和 tt，其中 tt 为禁止放置的格子的数量。
接下来 tt 行每行包含两个整数 xx 和 yy，表示位于第 xx 行第 yy 列的格子禁止放置，行列数从 11 开始。
输出格式
输出一个整数，表示结果。
数据范围
1≤N≤1001≤N≤100,
0≤t≤100
分析:
初始化：
标记障碍物位置。
将所有格子的匹配状态初始化为未匹配。
遍历白色格子：
仅处理 i+j 为奇数的白色格子（避免重复处理黑白格子）。
寻找增广路径：
对每个白色格子 (x,y)，尝试向四个方向扩展：
若相邻黑色格子 (a,b) 未被访问过且非障碍物：
标记该格子为已访问。
若该黑色格子未匹配，或其已匹配的白色格子能找到新的匹配路径，则更新匹配关系。
更新匹配数：
每次成功找到增广路径后，匹配数加一。
4. 算法正确性
二分图性质：黑白格子的相邻关系天然构成二分图，确保匈牙利算法的适用性。
增广路径原理：通过递归回溯，不断调整匹配关系，保证每次匹配数最大化。
5. 复杂度分析
时间复杂度：O(n^2 * n^2)，每个白色格子最多尝试 n^2 次扩展。
空间复杂度：O(n^2)，存储匹配状态和访问标记。
代码:
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool find(int x, int y)
{
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a && a <= n && b && b <= n && !g[a][b] && !st[a][b])
{
st[a][b] = true;
PII t = match[a][b];
if (t.x == -1 || find(t.x, t.y))
{
match[a][b] = {x, y};
return true;
}
}
}
return false;
}
int main()
{
cin >> n >> m;
while(m--)
{
int x,y;
cin >> x >> y;
g[x][y] = true;
}
memset(match,-1,sizeof match);
int res = 0;
for(int i=1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
if((i+j)%2 && !g[i][j])
{
memset(st,0,sizeof st);
if(find(i,j))res++;
}
}
}
cout << res << endl;
return 0;
}
机器任务(最小覆盖点==最大匹配边(二分图中))
有两台机器 A，BA，B 以及 KK 个任务。
机器 AA 有 NN 种不同的模式（模式 0∼N−10∼N−1），机器 BB 有 MM 种不同的模式（模式 0∼M−10∼M−1）。
两台机器最开始都处于模式 00。
每个任务既可以在 AA 上执行，也可以在 BB 上执行。
对于每个任务 ii，给定两个整数 a[i]a[i] 和 b[i]b[i]，表示如果该任务在 AA 上执行，需要设置模式为 a[i]a[i]，如果在 BB 上执行，需要模式为 b[i]b[i]。
任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
求怎样分配任务并合理安排顺序，能使机器重启次数最少。
输入格式
输入包含多组测试数据。
每组数据第一行包含三个整数 N,M,KN,M,K。
接下来 KK 行，每行三个整数 i,a[i]i,a[i] 和 b[i]b[i]，ii 为任务编号，从 00 开始。
当输入一行为 00 时，表示输入终止。
输出格式
每组数据输出一个整数，表示所需的机器最少重启次数，每个结果占一行。
数据范围
N,M<100,K<1000N,M<100,K<1000
0≤a[i]<N0≤a[i]<N
0≤b[i]<M
分析:
代码:
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m, k;
int match[N];
bool g[N][N], st[N];
bool find(int x)
{
for(int i=0;i<m;i++)
{
if(!st[i] && g[x][i])//没访问过,且有边
{
st[i] = true;//访问标记
if(match[i]==-1||find(match[i]))//如果没匹配过 or 匹配的可以换人
{
match[i]=x;//标记匹配 这条边,也就是这个任务可以被x这个点覆盖/
return true;
}
}
}
return false;
}
int main()
{
while (cin >> n, n)
{
cin >> m >> k;
memset(g, 0, sizeof g);
memset(match, -1, sizeof match);
while (k -- )
{
int t, a, b;
cin >> t >> a >> b;
if (!a || !b) continue;
g[a][b] = true;
}
int res = 0;
for (int i = 0; i < n; i ++ )
{
memset(st, 0, sizeof st);
if (find(i)) res ++ ;
}
cout << res << endl;
}
return 0;
}
骑士放置(棋盘二分图+最大独立集):
给定一个 N×MN×M 的棋盘，有一些格子禁止放棋子。
问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。
输入格式
第一行包含三个整数 N,M,TN,M,T，其中 TT 表示禁止放置的格子的数量。
接下来 TT 行每行包含两个整数 xx 和 yy，表示位于第 xx 行第 yy 列的格子禁止放置，行列数从 11 开始。
输出格式
输出一个整数表示结果。
数据范围
1≤N,M≤100
分析:
棋盘划分：将 n 行 m 列的棋盘上的格子依据 (i + j) 的奇偶性划分为两个集合，就像国际象棋棋盘的黑白格那样，从而构建出二分图。
边的定义：若一个格子能通过马走 “日” 的规则到达另一个非障碍物格子，并且这两个格子属于不同的集合，那么它们之间存在一条边。
输入与初始化
- 输入处理：运用
scanf读取棋盘的行数n、列数m以及障碍物的数量k- 借助
while循环读取每个障碍物的坐标(x, y)，并把g[x][y]标记为true，以此表明该位置是障碍物。
- 借助
- 数组初始化：
g[N][N]：二维布尔数组，用于标记棋盘上每个格子是否为障碍物。st[N][N]：二维布尔数组，在寻找增广路径时，用于标记某个格子是否已经被访问过，防止重复访问。mat[N][N]：二维pii类型数组，存储每个格子的匹配信息，mat[i][j]表示与格子(i, j)匹配的格子坐标。
3. 匈牙利算法寻找最大匹配
find函数：- 该函数的作用是为格子
(x, y)寻找一个匹配的格子。 - 遍历马走 “日” 的 8 个方向，计算新的坐标
(xx, yy)。 - 检查新坐标是否在棋盘范围内（
1 <= xx <= n且1 <= yy <= m），是否为障碍物（g[xx][yy]），以及是否已经被访问过（st[xx][yy]）。 - 若满足条件，标记该格子为已访问（
st[xx][yy] = 1），并获取该格子当前的匹配信息(px, py)。 - 如果该格子未匹配（
px == 0），或者可以通过递归调用find(px, py)为其当前匹配的格子找到新的匹配，则更新匹配信息（mat[xx][yy] = {x, y}），并返回true表示匹配成功；否则返回false。
- 该函数的作用是为格子
- 遍历棋盘：
- 在
main函数中，遍历棋盘上的所有格子(i, j)。 - 若该格子是障碍物（
g[i][j]）或者i + j为奇数，则跳过该格子。 - 对于符合条件的格子，调用
find函数尝试匹配，每次匹配成功则将匹配数res加 1。
- 在
4. 结果计算与输出
通过 n * m - tmp - res 计算未被匹配且非障碍物的格子数量。其中，n * m 是棋盘上格子的总数，tmp 是障碍物的数量，res 是最大匹配数。最后将计算结果输出。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=110;
bool st[N][N],g[N][N];
pii mat[N][N];
int n,m,k;
int dy[8]={1,2,2,1,-1,-2,-2,-1};
int dx[8]={2,1,-1,-2,-2,-1,1,2};
int find(int x,int y){
for(int i=0;i<8;i++){
int xx=dx[i]+x,yy=y+dy[i];
if(xx<1||xx>n||yy<1||yy>m) continue;
if(st[xx][yy]||g[xx][yy])continue;
st[xx][yy]=1;
int px=mat[xx][yy].first;
int py=mat[xx][yy].second;
if(px==0||find(px,py)){
mat[xx][yy]={x,y};
return true;
}
}
return false;
}
int main(){
scanf("%d %d %d",&n,&m,&k);
int tmp=k;
while(k--){
int x,y;
cin>>x>>y;
g[x][y]=true;
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]||(i+j)%2)continue;
memset(st,0,sizeof st);
if(find(i,j))res++;
}
}
cout<<n*m-tmp-res;
}
vani和cl2的捉迷藏(最小重复路径点覆盖)
Vani 和 cl2 在一片树林里捉迷藏。
这片树林里有 NN 座房子，MM 条有向道路，组成了一张有向无环图。
树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。
如果从房子 AA 沿着路走下去能够到达 BB，那么在 AA 和 BB 里的人是能够相互望见的。
现在 cl2 要在这 NN 座房子里选择 KK 座作为藏身点，同时 Vani 也专挑 cl2 作为藏身点的房子进去寻找，为了避免被 Vani 看见，cl2 要求这 KK 个藏身点的任意两个之间都没有路径相连。
为了让 Vani 更难找到自己，cl2 想知道最多能选出多少个藏身点。
输入格式
输入数据的第一行是两个整数 NN 和 MM。
接下来 MM 行，每行两个整数 x,yx,y，表示一条从 xx 到 yy 的有向道路。
输出格式
输出一个整数，表示最多能选取的藏身点个数。
分析:
整体思路概述
这段代码的核心目标是求解一个有向图的最小路径覆盖问题，通过将其转化为二分图最大匹配问题来解决。具体来说，先根据输入构建有向图的邻接矩阵，再利用 Floyd-Warshall 算法进行传递闭包运算，最后使用匈牙利算法求解二分图的最大匹配数，从而得到最小路径覆盖数。
详细步骤分析
1. 数据输入与图的初始化
输入读取：在 main 函数中，首先使用 scanf 读取节点数量 n 和边的数量 m。接着，通过 while 循环读取每条边的起点 u 和终点 v，并将邻接矩阵 g[u][v] 标记为 1，以此构建有向图。
邻接矩阵 g：g[N][N] 用于存储有向图的边信息，g[i][j] 为 1 表示存在从节点 i 到节点 j 的有向边，为 0 则表示不存在。
标记数组 st：st[N] 用于在匈牙利算法中标记节点是否已被访问，避免重复访问。
匹配数组 mat：mat[N] 用于记录每个节点的匹配信息，mat[i] 存储与节点 i 匹配的节点编号。
2. Floyd-Warshall 算法求传递闭包
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
g[i][j] = g[i][k] || g[k][j];
}
原理：Floyd-Warshall 算法是一种动态规划算法，用于求解图中任意两点之间的可达性。这里通过三重循环更新邻接矩阵 g，如果存在从节点 i 到节点 k 的路径，并且存在从节点 k 到节点 j 的路径，那么就认为存在从节点 i 到节点 j 的路径，将 g[i][j] 标记为 1。
作用：经过传递闭包运算后，g[i][j] 为 1 表示从节点 i 可以间接或直接到达节点 j，这样可以将图的可达性信息完整地记录下来，方便后续的匹配操作。
3. 匈牙利算法求解二分图最大匹配
find 函数：
该函数的作用是尝试为节点 x 寻找一个匹配的节点。
遍历所有节点 i，如果节点 i 已经被访问过（st[i] 为 true），则跳过该节点。
标记节点 i 为已访问（st[i] = true），并检查是否存在从节点 x 到节点 i 的路径（g[x][i] 为 1）。
如果节点 i 未匹配（mat[i] 为 0），或者可以通过递归调用 find(mat[i]) 为其当前匹配的节点找到新的匹配，则更新匹配信息（mat[i] = x），并返回 true 表示匹配成功；否则返回 false。
遍历节点寻找匹配：在 main 函数中，遍历所有节点 i，每次调用 find 函数前将 st 数组清零，确保每次寻找匹配时标记信息是干净的。如果 find(i) 返回 true，说明为节点 i 找到了匹配的节点，将匹配数 res 加 1。
4. 计算最小路径覆盖数
在有向无环图中，最小路径覆盖数等于节点数减去二分图的最大匹配数。这里最终输出的 res 即为二分图的最大匹配数，而最小路径覆盖数在本题代码中虽未单独计算输出，但根据原理可知最小路径覆盖数为 n - res。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=210;
bool g[N][N],st[N];
int n,m;
int mat[N];
bool find(int x){
for(int i=1;i<=n;i++){
if(!g[x][i])continue;
if(i==x)continue;
if(st[i])continue;
st[i]=true;//标记考虑过
if(!mat[i]||find(mat[i])){//没对象 or 可以再找一个
mat[i]=x;
return true;//返回
}
}
return false;
}
int main(){
scanf("%d %d",&n,&m);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
g[u][v]=1;//读入边
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
g[i][j]=g[i][j]||(g[i][k]&&g[k][j]);//传递闭包
}
int res=0;
for(int i=1;i<=n;i++){//考虑每个点
memset(st,0,sizeof st);
if(find(i))res++;//
}
cout<<n-res;
}