二分图的验证
bfs染色法
二分图最大匹配
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1005; bool road[N][N], used[N]; int match[N], n, m, e; /* 关于定义 road[i][j] == 1表示左边集合中的i到右边集合中的j有边 used[i] == 1是在每次做增广的时候记录已访问右集合的节点i match[i]记录右集合节点j的匹配对象 n, m, e如题 （左集合大小，右集合大小， 边数） */ bool dfs(int x) { for(int i = 1; i <= m; ++i) if(!used[i] && road[x][i])//判断这条边是否可以走 { used[i] = 1;//记录这个节点已经被访问 防止成环 if(!match[i] || dfs(match[i])) {//如果这个点可以被让出来 match[i] = x; return true;//记录新的匹配点 返回true } } return false;//匹配失败 } int main(){ scanf("%d%d%d", &n, &m, &e); for(int i = 1, x, y; i <= e; ++i) { scanf("%d%d", &x, &y); road[x][y] = 1; } int ans = 0;//答案 for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) used[j] = 0;//每次查询前都要清空used if(dfs(i)) ++ans; //如果这个点可以找到匹配点的话 答案加一 } printf("%d", ans); return 0; }
（左/右集合的）最大匹配
完美匹配
最小顶点覆盖：
用最少的顶点，覆盖全部的边
等于最大匹配数
最大点独立集：
一个点的集合，里面每两个点都没有边相连
等于点的个数，减去最大匹配
（把匹配拆了，剩下点数多的那一边，再加上不匹配，就是跟另一边不连通的点就行）
最小边覆盖：
用最少的边，覆盖所有点
等于最大点独立集
（独立的点不能互相连，就和外面连起来）
------------------------------------------
刷题的时候看到的
即得易见平凡，仿照上例显然。
留作习题答案略，读者自证不难。
反之亦然同理，结论自然成立。
略去过程QED，由上可知证毕。