二分图的匹配问题()-其他
二分图的匹配问题()
链接1
链接2
链接3
二分图
把一个无向图的点分为两个集合
图中的每条边的两个端点分别属于两个集合
所以，二分图中没有奇数个数点的环
判定
用染色法dfs或bfs
从一个未染色的点出发
枚举它的边
如果他的下一个点颜色与他相同
则该图不是二分图
如果下一个点为未染色
则搜索它
二分图的匹配
选定二分图中的一些边
如果这些边的两个端点都没有重复
（每个点在一个匹配中只出现一次）
则称它们为二分图的匹配
最大匹配
边数最多的匹配
完美匹配
图中每个点都为匹配点
匈牙利算法
增广路
从一个非匹配点开始
依次经过：
非匹配边 匹配边 非匹配边 匹配边……非匹配边
终点也为非匹配点
则这条路为增广路
将增广路中的边取反可以将二分图的匹配变大
没有增广路的匹配就是最大匹配
算法实现
通过不断找增广路来寻找最大匹配
code（dfs)
一个二分图
左边集合是1~n
右边集合是1+n~2n
bool dfs(int u){
for(int i=head[u];i;i=last[i]){
if(vis[to[i]])continue;
vis[to[i]]=1;
if(!match[to[i]] || dfs(match[to[i]])){//如果下一个点未匹配，那么直接找到增广路，否则跳到下一个点的对应匹配点（也就是两个两个点跳）
match[to[i]]=u;
return true;
}
}
return false;
}
void solve(){
for(int i=1;i<=n;i++){//只用枚举一个集合的点
memset(vis,0,sizeof(vis));//vis数组防止死循环
if(dfs(i))
ans++;//记录最大匹配数
}
return;
}
邻接矩阵O(\(n^3\))
邻接表O(\(n^2\)m)
最小点覆盖
选取一些点
与这些点直接连接的点是覆盖点
（它们自己也是覆盖点）
选取最少的点覆盖全图就是最小点覆盖
最小点覆盖=最大匹配
KM算法
链接1
链接2
KM算法
寻找二分图最大权完美匹配
流程
首先左集合的点有一个期望值（顶标）
为它到右集合的点的边的最大值
右集合的期望值为0
接着对每个左集合点进行操作
首先寻找在期望范围内的右点（边的权值=左期望+右期望）
枚举所有可能的边
进行类似于匈牙利算法的操作（操作时只使用在期望范围内的边）
尝试寻找增广路
如果没找到
那么只能降低期望
当然降低最少的期望
使得左集合中的一些点多出一些可选边
同时为了让原来的边依然可选
应该将左集合的点降低最少期望
右集合的点增加最少期望
由于没有找到增广路
所以路径上左点比右点多一
等同于总期望也降低了最少期望
如果还没有找到
继续重复操作（降低期望）
直到找到增广路
因为是完美匹配
每个点肯定都能找到增广路
code（DFS）假的O(\(n^3\))真的O(\(n^4\))
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=510;
ll read(){
ll x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
ll n,m;
ll slack[N],match[N],mp[N][N],va[N],vb[N],la[N],lb[N],ans;
bool dfs(int x){
va[x]=1;
for(int y=1;y<=n;y++){
if(vb[y])continue;
ll delta=la[x]+lb[y]-mp[x][y];
if(!delta){
vb[y]=1;
if(!match[y] || dfs(match[y])){
match[y]=x;
return true;
}
}
else slack[y]=min(slack[y],cha);
}
return false;
}
void KM(){
for(int i=1;i<=n;i++){
la[i]=mp[i][1];
for(int j=2;j<=n;j++)
la[i]=max(la[i],mp[i][j]);
}//左集合的顶标初始值
for(int i=1;i<=n;i++){
memset(slack,127,sizeof(slack));//记录没法被选的点离被选的最小距离
while(1){
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));//标记
if(dfs(i))break;
ll minn=INT_MAX;
for(int i=1;i<=n;i++)if(!vb[i])minn=min(minn,slack[i]);
for(int i=1;i<=n;i++)if(va[i])la[i]-=minn;
for(int i=1;i<=n;i++)if(vb[i])lb[i]+=minn;//降低期望（顶标）
}
}
for(int i=1;i<=n;i++)ans+=mp[match[i]][i];
return;
}
int main(){
memset(mp,128,sizeof(mp));
n=read(),m=read();
for(int i=1;i<=m;i++){
ll t1=read(),t2=read(),t3=read();
mp[t1][t2]=t3;//记录边
}
KM();
printf("%lld\n",ans);
for(int i=1;i<=n;i++)printf("%d ",match[i]);
return 0;
}
code(BFS)
首先为什么要优化
因为dfs的KM每次找不到完美匹配后就要重置vis
并从头开始搜
但要是能顺着上次继续搜，从新加入的边开始
就可以优化
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=510,inf=-200000000;
ll read(){
ll x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
ll n,m;
ll slack[N],match[N],mp[N][N],va[N],vb[N],la[N],lb[N],ans,pre[N],match2[N];
void aug(ll u){
while(u){
ll t=match2[pre[u]];
match2[pre[u]]=u;//match2[i]=j表示左点i目前匹配右点j
match[u]=pre[u];//match[i]=j表示右点i目前匹配左点j
u=t;//画个图可以明白
}
return;
}//这是一个更新，因为bfs没法回溯，所以用pre[i]=j记录右边的i来自于左边的j
void bfs(ll u){
queue<ll>q;
memset(slack,127,sizeof(slack));
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
q.push(u);
while(1){
while(!q.empty()){
ll x=q.front();q.pop();
va[x]=1;
for(ll y=1;y<=n;y++){
if(vb[y] || mp[x][y]==inf)continue;//没有路mp[x][y]==inf
ll delta=la[x]+lb[y]-mp[x][y];
if(delta<slack[y]){
pre[y]=x;//不管有没有这条路先记录路径，万一后面加边后y会进入队列
slack[y]=delta;
if(!delta){
vb[y]=1;
if(!match[y]){
aug(y);
return;
}
else q.push(match[y]);
}
}
}
}
ll minn=INT_MAX;
for(ll i=1;i<=n;i++)if(!vb[i])minn=min(minn,slack[i]);
for(ll i=1;i<=n;i++)if(va[i])la[i]-=minn;
for(ll i=1;i<=n;i++)if(vb[i])lb[i]+=minn; else slack[i]-=minn;//这里直接更新slack，因为后面判断新搜的点就是用slack=0
for(ll i=1;i<=n;i++){
if(!vb[i] && slack[i]==0){
vb[i]=1;
if(!match[i]){
aug(i);
return;
}
else q.push(match[i]);//把新边可以到的新点加入队列
}
}
}
return;
}
void KM(){
for(ll i=1;i<=n;i++){
la[i]=mp[i][1];
for(ll j=2;j<=n;j++)
la[i]=max(la[i],mp[i][j]);
}
for(ll i=1;i<=n;i++)bfs(i);
for(ll i=1;i<=n;i++)ans+=mp[match[i]][i];
return;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j]=inf;
for(ll i=1;i<=m;i++){
ll t1=read(),t2=read(),t3=read();
mp[t1][t2]=t3;
}
KM();
printf("%lld\n",ans);
for(ll i=1;i<=n;i++)printf("%lld ",match[i]);
return 0;
}
————————
链接1
链接2
链接3
二分图
把一个无向图的点分为两个集合
图中的每条边的两个端点分别属于两个集合
所以，二分图中没有奇数个数点的环
判定
用染色法dfs或bfs
从一个未染色的点出发
枚举它的边
如果他的下一个点颜色与他相同
则该图不是二分图
如果下一个点为未染色
则搜索它
二分图的匹配
选定二分图中的一些边
如果这些边的两个端点都没有重复
（每个点在一个匹配中只出现一次）
则称它们为二分图的匹配
最大匹配
边数最多的匹配
完美匹配
图中每个点都为匹配点
匈牙利算法
增广路
从一个非匹配点开始
依次经过：
非匹配边 匹配边 非匹配边 匹配边……非匹配边
终点也为非匹配点
则这条路为增广路
将增广路中的边取反可以将二分图的匹配变大
没有增广路的匹配就是最大匹配
算法实现
通过不断找增广路来寻找最大匹配
code（dfs)
一个二分图
左边集合是1~n
右边集合是1+n~2n
bool dfs(int u){
for(int i=head[u];i;i=last[i]){
if(vis[to[i]])continue;
vis[to[i]]=1;
if(!match[to[i]] || dfs(match[to[i]])){//如果下一个点未匹配，那么直接找到增广路，否则跳到下一个点的对应匹配点（也就是两个两个点跳）
match[to[i]]=u;
return true;
}
}
return false;
}
void solve(){
for(int i=1;i<=n;i++){//只用枚举一个集合的点
memset(vis,0,sizeof(vis));//vis数组防止死循环
if(dfs(i))
ans++;//记录最大匹配数
}
return;
}
邻接矩阵O(\(n^3\))
邻接表O(\(n^2\)m)
最小点覆盖
选取一些点
与这些点直接连接的点是覆盖点
（它们自己也是覆盖点）
选取最少的点覆盖全图就是最小点覆盖
最小点覆盖=最大匹配
KM算法
链接1
链接2
KM算法
寻找二分图最大权完美匹配
流程
首先左集合的点有一个期望值（顶标）
为它到右集合的点的边的最大值
右集合的期望值为0
接着对每个左集合点进行操作
首先寻找在期望范围内的右点（边的权值=左期望+右期望）
枚举所有可能的边
进行类似于匈牙利算法的操作（操作时只使用在期望范围内的边）
尝试寻找增广路
如果没找到
那么只能降低期望
当然降低最少的期望
使得左集合中的一些点多出一些可选边
同时为了让原来的边依然可选
应该将左集合的点降低最少期望
右集合的点增加最少期望
由于没有找到增广路
所以路径上左点比右点多一
等同于总期望也降低了最少期望
如果还没有找到
继续重复操作（降低期望）
直到找到增广路
因为是完美匹配
每个点肯定都能找到增广路
code（DFS）假的O(\(n^3\))真的O(\(n^4\))
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=510;
ll read(){
ll x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
ll n,m;
ll slack[N],match[N],mp[N][N],va[N],vb[N],la[N],lb[N],ans;
bool dfs(int x){
va[x]=1;
for(int y=1;y<=n;y++){
if(vb[y])continue;
ll delta=la[x]+lb[y]-mp[x][y];
if(!delta){
vb[y]=1;
if(!match[y] || dfs(match[y])){
match[y]=x;
return true;
}
}
else slack[y]=min(slack[y],cha);
}
return false;
}
void KM(){
for(int i=1;i<=n;i++){
la[i]=mp[i][1];
for(int j=2;j<=n;j++)
la[i]=max(la[i],mp[i][j]);
}//左集合的顶标初始值
for(int i=1;i<=n;i++){
memset(slack,127,sizeof(slack));//记录没法被选的点离被选的最小距离
while(1){
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));//标记
if(dfs(i))break;
ll minn=INT_MAX;
for(int i=1;i<=n;i++)if(!vb[i])minn=min(minn,slack[i]);
for(int i=1;i<=n;i++)if(va[i])la[i]-=minn;
for(int i=1;i<=n;i++)if(vb[i])lb[i]+=minn;//降低期望（顶标）
}
}
for(int i=1;i<=n;i++)ans+=mp[match[i]][i];
return;
}
int main(){
memset(mp,128,sizeof(mp));
n=read(),m=read();
for(int i=1;i<=m;i++){
ll t1=read(),t2=read(),t3=read();
mp[t1][t2]=t3;//记录边
}
KM();
printf("%lld\n",ans);
for(int i=1;i<=n;i++)printf("%d ",match[i]);
return 0;
}
code(BFS)
首先为什么要优化
因为dfs的KM每次找不到完美匹配后就要重置vis
并从头开始搜
但要是能顺着上次继续搜，从新加入的边开始
就可以优化
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=510,inf=-200000000;
ll read(){
ll x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
ll n,m;
ll slack[N],match[N],mp[N][N],va[N],vb[N],la[N],lb[N],ans,pre[N],match2[N];
void aug(ll u){
while(u){
ll t=match2[pre[u]];
match2[pre[u]]=u;//match2[i]=j表示左点i目前匹配右点j
match[u]=pre[u];//match[i]=j表示右点i目前匹配左点j
u=t;//画个图可以明白
}
return;
}//这是一个更新，因为bfs没法回溯，所以用pre[i]=j记录右边的i来自于左边的j
void bfs(ll u){
queue<ll>q;
memset(slack,127,sizeof(slack));
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
q.push(u);
while(1){
while(!q.empty()){
ll x=q.front();q.pop();
va[x]=1;
for(ll y=1;y<=n;y++){
if(vb[y] || mp[x][y]==inf)continue;//没有路mp[x][y]==inf
ll delta=la[x]+lb[y]-mp[x][y];
if(delta<slack[y]){
pre[y]=x;//不管有没有这条路先记录路径，万一后面加边后y会进入队列
slack[y]=delta;
if(!delta){
vb[y]=1;
if(!match[y]){
aug(y);
return;
}
else q.push(match[y]);
}
}
}
}
ll minn=INT_MAX;
for(ll i=1;i<=n;i++)if(!vb[i])minn=min(minn,slack[i]);
for(ll i=1;i<=n;i++)if(va[i])la[i]-=minn;
for(ll i=1;i<=n;i++)if(vb[i])lb[i]+=minn; else slack[i]-=minn;//这里直接更新slack，因为后面判断新搜的点就是用slack=0
for(ll i=1;i<=n;i++){
if(!vb[i] && slack[i]==0){
vb[i]=1;
if(!match[i]){
aug(i);
return;
}
else q.push(match[i]);//把新边可以到的新点加入队列
}
}
}
return;
}
void KM(){
for(ll i=1;i<=n;i++){
la[i]=mp[i][1];
for(ll j=2;j<=n;j++)
la[i]=max(la[i],mp[i][j]);
}
for(ll i=1;i<=n;i++)bfs(i);
for(ll i=1;i<=n;i++)ans+=mp[match[i]][i];
return;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j]=inf;
for(ll i=1;i<=m;i++){
ll t1=read(),t2=read(),t3=read();
mp[t1][t2]=t3;
}
KM();
printf("%lld\n",ans);
for(ll i=1;i<=n;i++)printf("%lld ",match[i]);
return 0;
}