二分图,即对于一个图$g=(V,E)$,将节点分成两个集合,使得$\forall e\in E$,它的两端点分别位于两个集合$A,B$中
对于二分图,有一些概念
匈牙利算法:
代码实现
class Solution {
public:
void constr_graph(int n,int m,vector<vector<int>> &broken,vector<vector<int>> &r){
vector<vector<int>> occupy(n,vector<int>(m));
for(auto b:broken){
occupy[b[0]][b[1]]=1;
}
// cout<<"=====occupy====="<<endl;
// for(int i=0;i<n;i++){
// cout<<i<<":";
// for(auto n:occupy[i]){
// cout<<n<<",";
// }
// cout<<endl;
// }
// cout<<"================"<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
// 首先把点分成两组,即奇数只能在pb,偶数只能在pa
if(i+j&1)continue;
if(occupy[i][j]!=0)continue;
int st=i*m+j;
if(i>0&&occupy[i-1][j]==0){
r[st].push_back((i-1)*m+j);
}
if(i<n-1&&occupy[i+1][j]==0){
r[st].push_back((i+1)*m+j);
}
if(j>0&&occupy[i][j-1]==0){
r[st].push_back(i*m+j-1);
}
if(j<m-1&&occupy[i][j+1]==0){
r[st].push_back(i*m+j+1);
}
}
}
}
int dfs(vector<vector<int>>&g,int st,vector<int> &vi,int dfn,vector<int>&pa,vector<int>&pb){
int m1=0,m2;
vi[st]=dfn;
for(auto i:g[st]){
if(pb[i]==-1){ // 如果另一个节点还没有连接任何边
pa[st]=i;
pb[i]=st;
return true;
}
}
// 如果所有节点都连接边了,表明自身是一个孤立的点,应该请求自身相连的点换边
for(auto i:g[st]){
// 当前路径深度优先换边
// 另一个节点没有到达这个深度,则给上一个连接的点更换连接对象尝试
if(vi[pb[i]]!=dfn&&dfs(g,pb[i],vi,dfn,pa,pb)){
pa[st]=i;
pb[i]=st;
return true;
}
}
return false;
}
int solve(vector<vector<int>> &g){
int mn=g.size(),dfn=0,r=0;
// cout<<"=====graph====="<<endl;
// for(int i=0;i<mn;i++){
// cout<<i<<":";
// for(auto n:g[i]){
// cout<<n<<",";
// }
// cout<<endl;
// }
// cout<<"================"<<endl;
vector<int> vis(mn),pa(mn,-1),pb(mn,-1);
while(true){
dfn++;
int cnt=0;
// 以3x3为例
// 第一轮循环:0->1,2->5,4->3,6->7,cnt=4
// 第二轮循环:没有,因为发现所有连接点都无法换边
for(int i=0;i<mn;i++){
// 本身没有加入集合并且成功匹配
if(pa[i]==-1&&dfs(g,i,vis,dfn,pa,pb)){
cnt++;
}
}
if(cnt==0)break;
r+=cnt;
}
return r;
}
int domino(int n, int m, vector<vector<int>>& broken) {
vector<vector<int>> g(m*n);
constr_graph(n,m,broken,g);
return solve(g);
}
};
简单理解增广路与匈牙利算法 - 朴楞蛾子的文章 - 知乎 https://zhuanlan.zhihu.com/p/208596378