二分图定义
二分图是一张无向图，可以分成 \(2\) 个集合 \(A\) 和 \(B\)。在同一个集合中的点没有边相连。
二分图判定
当且仅当图中不存在奇数环时，该图为二分图。
证明：反证法，构造一个奇数环。容易发现无论如何都不可能使相邻 \(2\) 点分到 \(2\) 个集合。
那么很容易想到一个判定二分图的方法：dfs染色法。
可以用 \(2\) 种颜色给图上的点进行染色。有边相连的点应该染成相反的颜色。如果在染色过程中出现冲突，则此图不是二分图。
示例代码：
bool dfs(int x,int c){
clr[x]=c;
for(int i=0;i<to[x].size();i++){
int v=to[x][i];
if(!vst[v]){
if(!dfs(v,3-c)) return 0;
}
else{
if(clr[v]==clr[x]) return 0;
}
}
return 1;
}
易证该算法的时间复杂度是 \(\Theta(n)\)。
例题1 P1525 关押罪犯。对于本题，我们希望分配到同一个监狱里的罪犯的最大仇恨值（即边权值）最小化，容易想到二分答案。
判定：存在一种方案，使得冲突影响力不超过mid。
该判定方法显然符合单调性（mid较小的方案，对于更大的mid一定可行）。
因此，如果我们忽略所有边权值小于mid的边后形成的图进行判定二分图成立，那么方案可行，继续二分mid，直到找到答案。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,maxx,ans;
vector<int> t[20009],a[20009];
int vst[20009];
bool Big=1;
void dfs(int u,int color,int num){
if(!Big) return ;
vst[u]=color;
for(int i=0;i<t[u].size();i++){
if(a[u][i]>num){
if(!vst[t[u][i]]) dfs(t[u][i],3-color,num);
else if(vst[t[u][i]]==color) Big=0;
}
}
return ;
}
bool ok(int num){
Big=1;
for(int i=1;i<=n;i++) vst[i]=0;
for(int i=1;i<=n&&Big;i++){
if(!vst[i]) dfs(i,1,num);
}
if(Big) return 1;
return 0;
}
int main(){
// freopen("prison.in","r",stdin);
// freopen("prison.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){
int pa,b,c;
cin>>pa>>b>>c;
t[pa].push_back(b);
a[pa].push_back(c);
t[b].push_back(pa);
a[b].push_back(c);
maxx=max(c,maxx);
}
int left=0,right=maxx,mid;
ans=right;
while(left<=right){
mid=(left+right)/2;
if(ok(mid))
{
if(ans>mid) ans=mid;
right=mid-1;
}
else left=mid+1;
}
cout<<ans;
return 0;
}
二分图匹配
匹配是一个边的集合 \(E\) ，满足任意 \(2\) 条边之间没有公共端点。而最大匹配即为二分图中，包含边数最多的一组匹配（\(max|E|\)）。
首先了解以下几个概念：
匹配边：\((x,y)∈E\)，反之称为非匹配边。
匹配点：如果 \((x,y)∈E\)，则 \(x\) 和 \(y\) 为匹配点。反之 \(x\) 和 \(y\) 为非匹配点。
交错路：一条非匹配边和匹配边交替经过的路径。
增广路：一边的非匹配点到另一边的非匹配点的交错路。
寻找二分图最大匹配的算法为匈牙利算法，算法步骤：
1.设 \(S\) 为空集，所有边都是非匹配边
2.寻找增广路path，如果找到，把所有路径上的边的匹配状态取反，得到一个更大的匹配。
3.重复第 \(2\) 步，直到图中不存在增广路。
寻找增广路：递归地从每个点 \(x\) 出发递归 \(y\) 寻找增广路。如果找到，一边回溯一边修改匹配状态。\(match[x]=y\)
要么 \(y\) 没有匹配点，要么 \(y\) 有匹配点，但是从 \(y\) 的匹配点出发递归去找增广路，可以找到。
dfs的时间复杂度为 \(\Theta(n)\)，匈牙利算法的时间复杂度为 \(\Theta(n^2)\)
示例代码：
#include<bits/stdc++.h>
using namespace std;
const int N=100009;
int n,m,ans,match[N];
vector<int> to[N];
bool vst[N];
bool dfs(int x){
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(vst[y]) continue;
if(!match[y]||dfs(match[y])){
match[y]=x;
return 1;
}
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
to[x].push_back(y);
to[y].push_back(x);
}
for(int i=1;i<=n;i++){
memset(vst,0,sizeof(vst)); //已经经过的点也要重新判断，每次都要清空vst数组
if(dfs(i)) ans++;
}
cout<<ans;
return 0;
}
例题1 T270574 棋盘覆盖。本题主要考察的是二分图建模，建模时要满足以下 \(2\) 个要求。
- 节点可以分成 \(2\) 个集合，集合内部的点没有边相连。
- 每个节点只能有 \(1\) 条边（匹配边）。
该题要求任意 \(2\) 张骨牌都不会重叠，即每个格子只能被 \(1\) 张骨牌覆盖，而每张骨牌可以覆盖 \(2\) 个格子。把骨牌看作边，格子看作点。
考虑把每个没有被禁止的格子分为 \(2\) 个不同的集合。
将格子像国际象棋棋盘交叉黑白染色，可以划分为 \(2\) 个不重叠的集合。黑色格子的行号+列号为奇数，白色格子的行号+列号为偶数。容易发现每个骨牌必然覆盖一个黑色格子和一个白色格子。
要求所需的最大骨牌数量，即求二分图最大匹配，用匈牙利算法。
时间复杂度为 \(\Theta(n^3)\)
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,t,ans;
int match[10009];
int to[2009][2009];
bool vst[10009];
int tot,To[400009],head[400009],nxt[400009];
void add(int u,int v){
To[++tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
bool ok(int x){
for(int i=head[x];i;i=nxt[i]){
int y=To[i];
if(vst[y]) continue;
vst[y]=1;
if(!match[y]||ok(match[y])){
match[y]=x;
return 1;
}
}
return 0;
}
int main(){
cin>>n>>t;
for(int i=1;i<=t;i++){
int x,y;
cin>>x>>y;
to[x][y]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<n;j++){
if(to[i][j]||to[i][j+1]) continue;
int u=(i-1)*n+j,v=u+1;
add(u,v);
add(v,u);
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++){
if(to[i][j]||to[i+1][j]) continue;
int u=(i-1)*n+j,v=i*n+j;
add(u,v);
add(v,u);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(to[i][j]||(i+j)%2) continue;
int u=(i-1)*n+j;
memset(vst,0,sizeof(vst));
ans+=ok(u);
}
}
cout<<ans;
return 0;
}
例题2 T270575 車的放置。首先显然每行每列只能有 \(1\) 个車。考虑构造行和列 \(2\) 个集合，車为连边，那么車的数量就是行和列的最大匹配边数。但要求有 \(T\) 个点不能放置，禁止点 \((i,j)\) 即行 \(i\) 和列 \(j\) 不能有连边。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,t,ans;
int match[209];
int to[209][209];
bool vst[209];
bool ok(int x){
for(int i=1;i<=m;i++){
if(!vst[i]&&!to[x][i]){
vst[i]=1;
if(!match[i]||ok(match[i])){
match[i]=x;
return 1;
}
}
}
return 0;
}
int main(){
cin>>n>>m>>t;
for(int i=1;i<=t;i++){
int x,y;
cin>>x>>y;
to[x][y]=1;
}
for(int i=1;i<=n;i++){
memset(vst,0,sizeof(vst));
ans+=ok(i);
}
cout<<ans<<endl;
return 0;
}
例题3 T311481 导弹防御塔。题目要求“最大时间最小化”，因此显然符合二分答案的单调性，考虑二分答案来解决此问题。
二分图的多重匹配，即给出一个包含 \(n\) 个左部节点和 \(m\) 个右部节点的二分图，从中选出尽量多的边，使第 \(i\) 个左部节点，最多和 \(x\) 条选出的边相连，使第 \(j\) 个右部节点最多 \(y\) 条选出的边相连。
当 \(x=y=1\) 时，就是二分图的最大匹配。
解决多重匹配有以下几种方案：
- 拆点：即把左部每个点拆成至多 \(x\) 个点，右部的点拆成至多 \(y\) 个点，套用最大匹配即可。
- 网络流，在此不多赘述。
对于本题，对于 \(m\) 个入侵者和 \(n\) 枚导弹 \(2\) 个集合，易证对于mid的时间，最多发射出 \(p=\frac{mid+T_2}{T_1+T_2}\) 枚导弹，即把 \(1\) 枚导弹拆成 \(p\) 枚导弹。但注意导弹在空中飞行也有时间，不一定在 \(mid\) 时间前发射的导弹就一定能在时间限制前摧毁目标。
因此本题思路为 二分+拆点建图+二分图最大匹配。时间复杂度为 \(\Theta(mnp+n^2)\)
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-9;
int n,m,match[4009];
double t1,t2,v,dist[59][59];
PII a[59],b[59];
bool vst[4009];
vector<int> to[59];
double get_dist(int i,int j){
double x=a[i].first-b[j].first;
double y=a[i].second-b[j].second;
return sqrt(x*x+y*y);
}
bool find(int x){
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(vst[y]) continue;
vst[y]=1;
if(!match[y]||find(match[y])){
match[y]=x;
return 1;
}
}
return 0;
}
bool check(double mid){
memset(match,0,sizeof(match));
for(int i=1;i<=m;i++){
memset(vst,0,sizeof(vst));
if(!find(i)) return 0;
}
return 1;
}
int main(){
cin>>n>>m>>t1>>t2>>v;
t1/=60;
for(int i=1;i<=m;i++){
cin>>a[i].first>>a[i].second;
}
for(int i=1;i<=n;i++){
cin>>b[i].first>>b[i].second;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
dist[i][j]=get_dist(i,j);
}
}
double l=0,r=1e9;
while(r-l>eps){
double mid=(l+r)/2;
int p=(mid+t2)/(t1+t2);
p=min(p,m);
for(int i=1;i<=m;i++){
to[i].clear();
for(int j=1;j<=n;j++){
for(int k=1;k<=p;k++){
if(k*t1+(k-1)*t2+dist[i][j]/v<mid-eps){
to[i].push_back((j-1)*p+k);
}
}
}
}
if(check(mid)) r=mid;
else l=mid;
}
cout<<fixed<<setprecision(6)<<r;
return 0;
}
二分图的最小点覆盖
对于二分图，最小点覆盖的点数等价于二分图的最大匹配包含的边数，即为König定理。
证明：
设二分图最小点覆盖的点数为 \(n\) ，最大匹配书边数为 \(m\)，证明 \(n=m\)
1.证明 \(n≥m\)
因为所有的 \(m\) 条匹配边之间没有公共点。而最小点覆盖想要覆盖这些匹配边，至少也得要 \(m\) 个点才能完全覆盖。
所以 \(n≥m\) 显然成立。
2.证明 \(n=m\) 可以取到
构造方案:恰好取了 \(m\) 个点,且这 \(m\) 个点能够将所有的边覆盖掉。
构造方式:
-
求出最大匹配,有 \(m\) 条匹配边。
-
从左部每个非匹配点出发,跑一遍增广路径,将路径上的所有点标记（这里增广路径一定不会成功,因为成功的话就不是最大匹配了,最大匹配后没有增广路径）。
-
选出左边所有未被标记的点和右边所有被标记的点。
那么如何证明这种构造方式得到的点数是 \(m\):
\((1)\) 明确有以下三个性质:
1.左边所有的非匹配点一定都被标记(因为每次构造是从左边非匹配点出发的,是起点)
2.右边所有的非匹配点一定没有被标记(因为右边非匹配点被标记的话,就会形成增广路径)
3.对于每个匹配边,左右两点要么同时被标记,要么同时不被标记(因为左边的匹配点一定是从右边某个匹配点过来的)。
\((2)\) 我们选择的是左边所有未被标记的点，则由性质 \(1\) 可知这些点一定是匹配点。
我们选择的是右边所有被标记的点，则由性质 \(2\) 可知这些点一定是匹配点。
所以我们选择的所有点一定是匹配边上的点。
\((3)\) 而对于每个匹配边,左右要么同时被标记,要么同时不被标记。
同时被标记的匹配边,由于我们选择了右边所有被标记的点,所以这些匹配边我们全选了。
同时不被标记的匹配边,由于我们选择了左边所有不被标记的点,所以这些匹配边我们全选了。
由 \((2),(3)\) 可知,我们的选择是所有的 \(m\) 条匹配边,且每个匹配边我们只会选择左,或者右边一个点。一共 \(m\) 个点。
所以这种构造方式得到的点数是 \(m\)。
接着证明这种构造方式覆盖了所有的边。
首先匹配边我们已知全部覆盖,因为由上面的证明我们可以知道 \(m\) 条边匹配边都被选了。
剩下的非匹配边有两种情况:
\((1)\) 左边的非匹配点连接右边的匹配点：
因为左边非匹配点我们都标记了,从这个非匹配点出发走增广路径,所以这样的边,它右边的匹配点也一定被标记,而右边被标记的点会被我们选择,所以我们选择的点会覆盖这样的边。
\((2)\) 左边匹配点连接右边非匹配点：
如果左边匹配点被标记,且有这样的一条边,那么走下去,右边的这个非匹配点也会被标记。与性质 \(2\) 右边所有非匹配点都不会被标记矛盾(存在增广路径)。
所以这样的边的左边匹配点一定不会被标记,那么它会被选中,所以这样的边也会被覆盖。
由 \((1),(2)\) 可知这种构造方式覆盖了所有的边。
综上,这种构造方式可以构造出用 \(m\) 个点覆盖所有的边的情况=最大匹配数,证明了等号可以取得。
所以 \(n=m\)，即最小点覆盖数=最大匹配数。
二分图最小点覆盖建模前提：每条边 \(2\) 个端点，并且每条边至少选择 \(1\) 个端点。
例题1 T311483 机器任务。把两台机器 \(A,B\) 看作 \(2\) 个集合，考虑二分图最小点覆盖的特点：每一条边的 \(2\) 个结点至少要选择 \(1\) 个，代入此题就是每个任务必须在 \(2\) 台机器中选择一台，要么用 \(a_i\) 模式，要么用 \(b_i\) 模式。因此本题答案显然为二分图最小点覆盖。
注意因为机器初始时为 \(0\) ，因此要把端点有 \(0\) 的点排除在外（不影响重启次数）。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
vector<int> to[100009];
int match[109];
bool vst[109];
bool hungary(int x){
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(vst[y]) continue;
vst[y]=1;
if(!match[y]||hungary(match[y])){
match[y]=x;
return 1;
}
}
return 0;
}
int main(){
while(cin>>n){
if(n==0) break;
cin>>m>>k;
for(int i=0;i<=n;i++) to[i].clear();
for(int i=1;i<=k;i++){
int j,a,b;
cin>>j>>a>>b;
if(a==0||b==0) continue;
to[a].push_back(b);
}
int ans=0;
for(int i=0;i<n;i++){
memset(vst,0,sizeof(vst));
if(hungary(i)) ans++;
}
cout<<ans<<endl;
}
return 0;
}
例题2 T311743 泥泞的区域。对于任意一个泥泞的格子 \((i,j)\)，要么是被横着盖，要么是被竖着盖，满足二分图最小点覆盖的建模前提。接下来将每一个泥泞的格子编横块号和列块号，将两个编号连起来，运行二分图最小点覆盖即可。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m;
char a[59][59];
int match[2509];
int b[59][59],c[59][59];
bool vst[2509];
vector<int> to[2509];
bool hungary(int x){
for(int i=0;i<to[x].size();i++){
int y=to[x][i];
if(vst[y]) continue;
vst[y]=1;
if(!match[y]||hungary(match[y])){
match[y]=x;
return 1;
}
}
return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>a[i][j];
}
int cnt1=1,cnt2=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='*') b[i][j]=cnt1;
else cnt1++;
}
cnt1++;
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(a[i][j]=='*') c[i][j]=cnt2;
else cnt2++;
}
cnt2++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='*'){
to[b[i][j]].push_back(c[i][j]);
}
}
}
int ans=0;
for(int i=1;i<=cnt1;i++){
memset(vst,0,sizeof(vst));
if(hungary(i)) ans++;
}
cout<<ans;
return 0;
}
二分图最大独立集
独立集：一个点集，其中任意 \(2\) 点之间都没有边相连。
最大独立集：点数最多的独立集。
二分图最大独立集 \(=\) \(n\) \(-\) 二分图最小点覆盖（最大匹配）
证明：求最大独立集的过程可以看作是删去数量最少的点和它们的连边，使得所有边都被删除，剩下的点就是最大独立集。而删去的点集即为最小点覆盖，因此二分图最大独立集和二分图最小点覆盖互为补集。
例题1 T311485 骑士放置。将棋盘交叉黑白染色，观察发现，当骑士在黑色格子内时，能攻击的点必定是白色格子，反之必定是黑色格子。满足二分图“同一个集合内的点必定没有连边”。连边意味着能攻击到，而本题要求的是最多放置多少个不能攻击的骑士，因此选出来的点不能有连边，即求二分图最大独立集。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
typedef pair<int,int> PII;
int cx[8]={2,2,-1,-1,1,1,-2,-2};
int cy[8]={-1,1,-2,2,-2,2,-1,1};
int n,m,t;
bool vst[109][109];
PII match[109][109];
int unable[109][109];
bool hungary(int x,int y){
for(int i=0;i<8;i++){
int nx=x+cx[i],ny=y+cy[i];
if(nx<1||nx>n||ny<1||ny>m||unable[nx][ny]||vst[nx][ny]) continue;
vst[nx][ny]=1;
if((match[nx][ny].first==0&&match[nx][ny].second==0)||hungary(match[nx][ny].first,match[nx][ny].second)){
match[nx][ny]=make_pair(x,y);
return 1;
}
}
return 0;
}
int main(){
cin>>n>>m>>t;
for(int i=1;i<=t;i++){
int x,y;
cin>>x>>y;
unable[x][y]=1;
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
memset(vst,0,sizeof(vst));
if(unable[i][j]||((i+j)&1)) continue;
if(hungary(i,j)) ans++;
}
}
cout<<n*m-ans-t;
return 0;
}