本文是写给作者自己看的
概念
指一张无向图G中，N个节点可以划分为两个集合A,B
集合A和B内部没有连边，A和B可以有连边（可以有空集）
Q：为什么不用三分图：
A：很简单，三分图分类更多，更麻烦。没有顺序关系有三种情况，有顺序关系则是六种（就像线段树不用三叉）
一些叫法
A集合内的点：左部点
B集合内的点：右部点
判定
充要条件：没有奇环
经典中的经典，显然要形成环，肯定是一个左部点，一个右部点......所以肯定是偶环。
具体实现：黑白染色，如果有相邻的点同色就不是二分图。
注意：图不一定连通！图不一定连通！图不一定连通！
模版：P1525 关押罪犯
其实可能用并查集的做法可能更广为人知，但是二分图更加直观。
你考虑这样一件事，就是说：可以二分一个阙值i，判断如果让影响力为i是否可行。那么就是让所有影响力大于i的罪犯二元组在不同的监狱里，显然，二分图匹配。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> v[20001];
struct stu{
int from,to,val;
}jail[100001];
int maxn=0;
int col[20001];
bool dfs(int now,int c){
col[now]=c;
for(int i=0;i<v[now].size();i++){
if(col[v[now][i]]){
if(col[v[now][i]]==col[now]) return false;//相邻节点相同颜色
}
else{
if(!dfs(v[now][i],3-c)) return false;//递归下去任何一条路径不满足要求都返回false,和后面的最大匹配很容易混淆
}
}
return true;
}
bool check(int now){
for(int i=1;i<=n;i++) v[i].clear(),col[i]=0;
for(int i=1;i<=m;i++){
if(jail[i].val>now){//所有影响力大于阙值的二元组
v[jail[i].from].push_back(jail[i].to);
v[jail[i].to].push_back(jail[i].from);
}
}
for(int i=1;i<=n;i++){
if(!col[i]){
if(!dfs(i,1)) return false;//图不一定连通！
}
}
return true;
}
int erfen(int l,int r){//交给二分
if(l==r) return l;
else if(l==r-1){
if(check(l)) return l;
else return r;
}
else{
int mid=(l+r)/2;
if(check(mid)) return erfen(l,mid);
else return erfen(mid+1,r);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>jail[i].from>>jail[i].to>>jail[i].val;
maxn=max(maxn,jail[i].val);
}
cout<<erfen(0,maxn);
return 0;
}
还可以练一练这个,思路不难：
CF85E Guard Towers
最大匹配
在一张二分图中选最多的不共点的边，边数就是最大匹配
怎么说呢，这东西网络流当然可以做。理论上来说，二分图的题目用网络流做都是有正确性的。
很多要输出方案并且数据范围比较小的时候基本实锤网络流。
匈牙利算法
广为人知的最大匹配算法
具体流程：
二分图的左部点向右部点连边。
枚举尚未匹配的左部点x，从x出发找增广路径到未匹配右部点y。注意，千万注意和前面的判定搞混了，最大匹配只要找到一条增广路径就可以。
二分图的最小点覆盖
在原图中选一个最小点集S,使得每一条边都至少有一个端点在S中。
(用最少的点覆盖所有的边)
和2-SAT区分，不是必须二选一，也可以二选二
konig 定理
o上面有两个点的，打不出来
二分图的最小点覆盖=二分图的最大匹配
证明：
首先，对于最大匹配中的每一条边，选一个点出来一定可以覆盖所有的边，由此可得二分图的最大匹配>=二分图的最小点覆盖
然后，让最小点覆盖点集里的每个点向外连一条边，可以覆盖所有的边。如果没有共点的边，数量等于最大匹配。如果有共点的，大于最小点覆盖，所以二分图的最大匹配<=二分图的最小点覆盖
综上，二分图的最小点覆盖=二分图的最大匹配
二分图的最小边覆盖
在原图中选一个最小边集S,使得每一点都为S中至少一条边的端点
二分图中最小边覆盖=顶点数-二分图最大匹配
二分图中最小边覆盖+最小顶点覆盖=顶点数。
最大独立集
在无向图中选取最大的点集S，S内任意2点之间都没有连边
二分图的最大独立集=总点数-最小点覆盖=总点数-最大匹配
证明：
显然把在最小点覆盖点集里的所有点删了以后剩余的点都不联通。于是二分图的最大独立集=总点数-最小点覆盖。
而前面证明了最小点覆盖=最大匹配
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n,r,c;
int tol;
vector<int> v[40001];
int match[40001];
bool vis[40001];
string s[210];
int ans;
bool ct[210][210];
bool hungray(int now){
for(int i=0;i<v[now].size();i++){
int to=v[now][i];
if(!vis[to]){
vis[to]=true;
if(!match[to] || hungray(match[to])){
match[to]=now;
return true;
}
}
}
return false;
}
int get(int xx,int yy){
return (xx-1)*n+yy;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
r=1,c=2;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
ct[a][b]=true;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!ct[i][j]){
tol++;
if(i+r<=n && j+c<=n && !ct[i+r][j+c]) v[get(i,j)].push_back(get(i+r,j+c));
if(i+c<=n && j+r<=n && !ct[i+c][j+r]) v[get(i,j)].push_back(get(i+c,j+r));
if(i+r<=n && j-c>=1 && !ct[i+r][j-c]) v[get(i,j)].push_back(get(i+r,j-c));
if(i+c<=n && j-r>=1 && !ct[i+c][j-r]) v[get(i,j)].push_back(get(i+c,j-r));
if(i-r>=1 && j+c<=n && !ct[i-r][j+c]) v[get(i,j)].push_back(get(i-r,j+c));
if(i-c>=1 && j+r<=n && !ct[i-c][j+r]) v[get(i,j)].push_back(get(i-c,j+r));
if(i-r>=1 && j-c>=1 && !ct[i-r][j-c]) v[get(i,j)].push_back(get(i-r,j-c));
if(i-c>=1 && j-r>=1 && !ct[i-c][j-r]) v[get(i,j)].push_back(get(i-c,j-r));
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if((i+j)%2==0 && !ct[i][j]){
memset(vis,0,sizeof(vis));
if(hungray(get(i,j))) ans++;
}
}
}
//cout<<tol<<endl;
cout<<tol-ans;
return 0;
}
模版：
P3355 骑士共存问题
把方格黑白染色。显然在黑色格子上的马只能攻击在白色格子上的点，反之亦然，显然是二分图。
有一个细节。匈牙利求最大匹配肯定是跑不满的，但是先连右下角更容易匹配上，常数小很多。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n,r,c;
int tol;
vector<int> v[40001];
int match[40001];
bool vis[40001];
string s[210];
int ans;
bool ct[210][210];
bool hungray(int now){
for(int i=0;i<v[now].size();i++){
int to=v[now][i];
if(!vis[to]){
vis[to]=true;
if(!match[to] || hungray(match[to])){
match[to]=now;
return true;
}
}
}
return false;
}
int get(int xx,int yy){
return (xx-1)*n+yy;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
r=1,c=2;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
ct[a][b]=true;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!ct[i][j]){
tol++;
if(i+r<=n && j+c<=n && !ct[i+r][j+c]) v[get(i,j)].push_back(get(i+r,j+c));
if(i+c<=n && j+r<=n && !ct[i+c][j+r]) v[get(i,j)].push_back(get(i+c,j+r));
if(i+r<=n && j-c>=1 && !ct[i+r][j-c]) v[get(i,j)].push_back(get(i+r,j-c));
if(i+c<=n && j-r>=1 && !ct[i+c][j-r]) v[get(i,j)].push_back(get(i+c,j-r));
if(i-r>=1 && j+c<=n && !ct[i-r][j+c]) v[get(i,j)].push_back(get(i-r,j+c));
if(i-c>=1 && j+r<=n && !ct[i-c][j+r]) v[get(i,j)].push_back(get(i-c,j+r));
if(i-r>=1 && j-c>=1 && !ct[i-r][j-c]) v[get(i,j)].push_back(get(i-r,j-c));
if(i-c>=1 && j-r>=1 && !ct[i-c][j-r]) v[get(i,j)].push_back(get(i-c,j-r));
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if((i+j)%2==0 && !ct[i][j]){
memset(vis,0,sizeof(vis));
if(hungray(get(i,j))) ans++;
}
}
}
//cout<<tol<<endl;
cout<<tol-ans;
return 0;
}
最大团
在无向图G中选取最大的点集S，S内任意两点之间都有直接连边
在一般图中，这是一个NP问题，但是在补图为二分图的时候就不一样了。
首先说一下补图的概念
补图
在无向图G中，原来连边的点不连边，得到补图G次
于是有一个显然的结论：原图的最大团等于补图的最大独立集
有向图最小路径点覆盖
在一张有向无环图DAG中，用最少的不相交的路径覆盖所有的点。
实现方法：
-
1.将原图中每一个点x拆为出点out[x]和入点in[x]
-
2.对于原图中一条x->y的有向边，在新图中连边out[x],in[y]
显然这是一张二分图
- 3.最小路径点覆盖=原图中的点数N-新图的最大匹配
证明：
首先可以认为有N条路径，我们要将它们合并。你考虑匹配的现实意义其实就是把两条路径首尾相接。也就是每匹配一次就少了一条路径。
也可以这么证明：
首先一条路径肯定是一条链。
那么一条路径只有1个入度为0的点和一个出度为0的点。所以路径最少等价于出度为0的点最少。如果出边被匹配一次出度为0的点就会减少一个
模版：
poj-2594 Treasure Exploration
#include<iostream>
#include<vector>
#define int long long
using namespace std;
int n,m;
vector<int> v[560];
int match[560];
bool dis[560][560];
bool vis[560];
int ans;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][k] && dis[k][j]) dis[i][j]=true;
}
}
}
}
bool hungray(int now){
for(int i=0;i<v[now].size();i++){
int to=v[now][i];
if(!vis[to]){
vis[to]=true;
if(!match[to] || hungray(match[to])){
match[to]=now;
return true;
}
}
}
return false;
}
signed main(){
while(cin>>n>>m){
ans=0;
if(!n && !m) break;
for(int i=1;i<=n;i++) v[i].clear(),match[i]=false;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=false;
}
}
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
dis[a][b]=true;
}
floyd();//传递闭包
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]) v[i].push_back(j);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) vis[j]=false;
if(hungray(i)) ans++;
}
cout<<n-ans<<endl;
}
return 0;
}
输出方案模版：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
vector<int> v[160];
int match[160];
int help[160];
bool vis[160];
int ans;
bool hungray(int now){
for(int i=0;i<v[now].size();i++){
int to=v[now][i];
if(!vis[to]){
vis[to]=true;
if(!match[to] || hungray(match[to])){
match[to]=now;
help[now]=to;
return true;
}
}
}
return false;
}
void out_put(int now){
while(help[now] && !vis[help[now]]){
vis[now]=true;
cout<<now<<" ";
now=help[now];
}
if(!vis[now]){
vis[now]=true;
cout<<now;
}
cout<<endl;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
v[a].push_back(b);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) vis[j]=false;
if(hungray(i)) ans++;
}
for(int i=1;i<=n;i++) vis[i]=false;
for(int i=1;i<=n;i++){
if(!match[i]) out_put(i);
}
cout<<n-ans;
return 0;
}
有向图最小可相交路径点覆盖
核心思想：转化为不相交的情况。将两点之间的间接到达转化为直接到达。
对，floyd求传递闭包，然后直接按不相交的方法跑
综合例题
eg1
一道很好的思维题。
假设有\(2* n\)个点分列两边，左部点i向右部点j连边表示(i,j)为1
此时最终的目标是有(1,1),(2,2),(3,3)...(n,n)这些边
考虑行交换和列交换的意义。
假设现在有(1,2),(2,1)，显然可以通过行列交换变成(1,1),(2,2)这两条边。画一个图，形象的理解就是把缠在一起的两条边绕开了，所以n条边缠在一起肯定可以把其变为目标状态。（当然，不能有(x,y),(z,y)这种情况出现）
所以，若最大匹配数为n则有解，反之无解。
eg2
P2526 [SHOI2001] 小狗散步
这道题比较典，看到这句话：“Pandog 每次与主人相遇之前最多只去一个景点”很容易想到匹配，然后是这句话：“使它能够游览最多的景点”，这相当于告诉我们一个景点只去一次。所以直接能赶回来就连边。