joomla! 1.5 网站建设基础教程,水产网站源码,广州工程建设信息网站,找网站做q币文章目录 二分染色#xff1a;257. 关押罪犯增广路径372. 棋盘覆盖 最小点覆盖376. 机器任务 最大独立集378. 骑士放置 最小路径点覆盖 二分染色#xff1a;257. 关押罪犯
257. 关押罪犯 - AcWing题库
最大最小问题#xff0c;一眼二分 答案的范围在 [ 1 , 1 e 9 ] [1, 1… 文章目录 二分染色257. 关押罪犯增广路径372. 棋盘覆盖 最小点覆盖376. 机器任务 最大独立集378. 骑士放置 最小路径点覆盖 二分染色257. 关押罪犯
257. 关押罪犯 - AcWing题库
最大最小问题一眼二分 答案的范围在 [ 1 , 1 e 9 ] [1, 1e9] [1,1e9]之间二分答案check(mid) check将所有权值大于mid的边进行二分若能得到二分图返回true否则返回false 最终将得到最优解ans所有大于ans的边组成的图为二分图若是图中有边的权值小于ans那么这个图就不是二分图 当ans为0时说明原图就是一张二分图此时的答案也为0不需要特判所以二分的区间为 [ 0 , 1 e 9 ] [0, 1e9] [0,1e9]
#include iostream
#include cstring
using namespace std;const int N 20010, M 2e5 10;
int h[N], e[M], ne[M], w[M], idx;
int color[N];
int n, m;void add(int x, int y, int d)
{e[idx] y, ne[idx] h[x], w[idx] d, h[x] idx ;
}bool dfs(int x, int c, int mid)
{color[x] c;for (int i h[x]; i ! -1; i ne[i]){if (w[i] mid) continue;int y e[i];if (!color[y]){if (!dfs(y, 3 - c, mid)) return false;}else if (color[y] c) return false;}return true;
}bool check(int mid)
{memset(color, 0, sizeof(color));for (int i 1; i n; i )if (!color[i])if (!dfs(i, 1, mid))return false;return true;
}int main()
{memset(h, -1, sizeof(h));scanf(%d%d, n, m);int x, y, d;for (int i 0; i m; i ){scanf(%d%d%d, x, y, d);add(x, y, d), add(y, x, d);}int l 0, r 1e9;while (l r){int mid l r 1;if (check(mid)) r mid;else l mid 1;}printf(%d\n, l);return 0;
}增广路径
从二分图的非匹配点开始经过非匹配边匹配边非匹配边匹配边…最后到非匹配点的路径被称为增广路径 将所有匹配边删除添加非匹配边图中匹配的对数1 最大匹配不存在增广路径 372. 棋盘覆盖
372. 棋盘覆盖 - AcWing题库
建图方式很特殊将每个格子看成点相邻格子之间连一条边问题就转换成了从图中选择最多的边使得每条边的点都不重复 这就是一个最大匹配问题 接着判断图是否是一个二分图若不是二分图那么不能使用匈牙利算法 将n*m矩阵的奇数格和偶数格横纵坐标之和染上不同的颜色相同颜色的为一组那么整个矩阵就能被分成两个集合由于只有相邻格子之间存在边所以集合中的不存在边只有集合之间存在边
枚举所有奇数格或者偶数格试着将其匹配。注意不需要枚举坏掉的格子匹配时也不用匹配坏掉的格子
#include iostream
#include cstring
using namespace std;const int N 110;
typedef pairint, int PII;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[4] { 0, 1, 0, -1 }, dy[4] { 1, 0, -1, 0 };
int n, m;bool find(int x, int y)
{for (int i 0; i 4; i ){int nx x dx[i], ny y dy[i];if (!g[nx][ny] nx 1 nx n ny 1 ny n){if (!st[nx][ny]){auto t match[nx][ny];st[nx][ny] true;if (t.first 0 || find(t.first, t.second)){match[nx][ny] { x, y };return true;}}}}return false;
}int main()
{scanf(%d%d, n, m);int x, y;while (m -- ){scanf(%d%d, x, y);g[x][y] true;}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, false, sizeof(st));if (find(i, j)) res ;}printf(%d\n, res);return 0;
}debugfind的判断条件if (!g[nx][ny] nx 1 nx n ny 1 ny n)的!g[nx][ny]写成了!g[x][y] 每次find之前st数组没有重置 最小点覆盖
给定一个无向图从中选出最少的点使得每条边只有一个端点被选择 结论最小点覆盖 最大匹配数 376. 机器任务
376. 机器任务 - AcWing题库
分析题意有k个任务每个任务可以在A机器或者B机器上完成但是机器必须调整为相应的模式任务的执行顺序任意求任意顺序中的最少调整次数
建图将完成每个任务需要调整的模式看成点一个任务有两个点在这两点之间连线。显然得到的图是一个二分图由于不同任务在相同机器上需要调整的模式可能相同这些点可以看成一个点 题目要完成所有任务即选择每条边的一个点根据题意也就是求最小点覆盖 用匈牙利求二分图的最大匹配即可 由于每台机器的初始状态为0所以需要调整状态为0的任务不用切换模式直接就能完成因此建图时不需要建立这些任务
#include iostream
#include cstring
using namespace std;const int N 210, M 1010;
int h[N], e[M], ne[M], idx;
int match[N]; bool st[N];
int n1, n2, m;void add(int x, int y)
{e[idx] y, ne[idx] h[x], h[x] idx ;
}bool find(int x)
{for (int i h[x]; i ! -1; i ne[i]){int y e[i];if (!st[y]){st[y] true;if (match[y] 0 || find(match[y])){match[y] x;return true;}}}return false;
}int main()
{while (scanf(%d, n1), n1){idx 0;memset(h, -1, sizeof(h));memset(match, 0, sizeof(match));scanf(%d%d, n2, m);int t, x, y;while (m -- ){scanf(%d%d%d, t, x, y);if (x 0 || y 0) continue;add(x, y);}int res 0;for (int i 1; i n1; i){memset(st, false, sizeof(st));if (find(i)) res ;}printf(%d\n, res);}return 0;
}最大独立集
从一个无向图中选出最多的点使得选出的点之间都没有边 等价于去掉最少的点将所有边破坏 等价于最小点覆盖等价于最大匹配 假设一共n个点最大匹配数位m最大独立集的数量为n - m 最大团 从一个无向图中选出最多的点使得选出的点之间都有边 378. 骑士放置
378. 骑士放置 - AcWing题库
建图矩阵中能互相攻击到的格子之间建立一条边 那么问题就转换成了求图的最大独立集即选择的格子之间都没有边不能相互攻击
验证建的图是否为二分图将奇数格和偶数格染不同的颜色若当前坐标为 ( x , y ) (x, y) (x,y)那么该坐标之和为 x y x y xy要得到与之相连的坐标就要将x±1y±2坐标之和要±一个奇数 假设坐标之和为奇数加上奇数得到偶数格子的颜色不同 假设坐标之和为偶数加上奇数得到奇数格子的颜色也不同 所以该图是一个二分图可以使用匈牙利算法求最大匹配
#include iostream
#include cstring
using namespace std;typedef pairint, int PII;
const int N 110;
bool g[N][N], st[N][N];
PII match[N][N];
int dx[8] { 1, 1, 2, 2, -1, -1, -2, -2 }, dy[8] { 2, -2, 1, -1, 2, -2, 1, -1 };
int n, m, t;bool find(int x, int y)
{for (int i 0; i 8; i ){int nx x dx[i], ny y dy[i];if (!g[nx][ny] nx 1 nx n ny 1 ny m){if (!st[nx][ny]){st[nx][ny] true;auto t match[nx][ny];if (t.first 0 || find(t.first, t.second)){match[nx][ny] { x, y };return true;}}}}return false;
}int main()
{scanf(%d%d%d, n, m, t);int x, y;for (int i 0; i t; i ){scanf(%d%d, 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){memset(st, 0, sizeof(st));if (find(i, j)) res ;}printf(%d\n, n * m - t- res);return 0;
}debug求最大匹配时只需要遍历一个集合中的点可以是奇数格也可以是偶数格即添加条件(i j) % 2 最小路径点覆盖
针对有向无环图用最少的互不相交点不重复的路径较所有点覆盖 没听懂先跳过
