二分图匹配问题

2024-11-29 技术教程

匈牙利算法

struct edge{int u,v;edge *next;}*head[N],e[N];void add(int u,int v){edge *p=&e[cnt++];p->u=u;p->v=v;p->next=head[u];head[u]=p;}bool dfs(int u){for(edge *p=head[u];p;p=p->next){ if(!vis[p->v]){ vis[p->v]=1; if(!y[p->v]||dfs(y[p->v])){// 如果u->v 可以连标记或者回溯到y[v]连的连其他的路 x[u]=p->v;y[p->v]=u;//找增广路 return true; } }}return false;}

最大匹配=最小点集最大独立集=最小边集(最小路径覆盖)=|V|-最大匹配KM算法

#include<bits/stdc++.h>#define me(a,x) memset(a,x,sizeof(a))using namespace std;typedef long long ll;typedef unsigned long long ull;const int mod=1e9+7;const int N=2e3+5;const int MAX=0x7fffffff;const int MIN=0x80000000;int nx,ny;int w[N][N],lx[N],ly[N];bool sx[N],sy[N];int match[N][N];bool dfs(int u){ sx[u]=true; for(int v=0;v<ny;v++){ int d=lx[u]+ly[v]-w[u][v]; if(!sy[v]&&!d){ sy[v]=true; if(match[v]==-1||dfs(match[v])){ match[v]=u;return true; } } }return false;}int KM(){ for(int i=0;i<nx;i++){ ly[i]=lx[i]=0; for(int j=0;j<ny;j++)lx[i]=max(lx[i],w[i][j]); } me(match,-1); for(int u=0;u<nx;u++){ while(true){ me(sx,0),me(sy,0); if(dfs(u))break; int dis=MAX; for(int i=0;i<nx;i++){ if(sx[i]){ for(int j=0;j<ny;j++){ if(!sy[j]){ dis=min(dis,lx[i]+ly[j]-w[i][j]); } } } } if(dis==0)continue; if(dis==MAX)return -1; for(int i=0;i<nx;i++){ if(sx[i])lx[i]-=dis; } for(int i=0;i<ny;i++){ if(sy[i])ly[i]+=dis; } } } int sum=0; for(int i=0;i<ny;i++){ if(match[i]>=0)sum+=w[match[i]][i]; }return sum;}

#include<bits/stdc++.h>#define me(a,x) memset(a,x,sizeof(a))using namespace std;typedef long long ll;typedef unsigned long long ull;const int mod=1e9+7;const int N=2e3+5;const int MAX=0x7fffffff;const int MIN=0x80000000;int nx,ny;int w[N][N],lx[N],ly[N];bool sx[N],sy[N];int match[N][N];int slack[N];bool dfs(int u){ sx[u]=true; for(int v=0;v<ny;v++){ int d=lx[u]+ly[v]-w[u][v]; if(!sy[v]&&!d){ sy[v]=true; if(match[v]==-1||dfs(match[v])){ match[v]=u;return true; } }else if(!sy[v]&&d)slack[i]=min(slack[i],d); }return false;}int KM(){ for(int i=0;i<nx;i++){ ly[i]=lx[i]=0; for(int j=0;j<ny;j++)lx[i]=max(lx[i],w[i][j]); } me(match,-1); for(int u=0;u<nx;u++){ for(int i=0;i<N;i++)slack[i]=MAX; while(true){ me(sx,0),me(sy,0); if(dfs(u))break; int dis=MAX; for(int i=0;i<ny;i++){ if(!sy[i])dis=min(dis,slack[i]); } if(dis==0)continue; if(dis==MAX)return -1; for(int i=0;i<nx;i++){ if(sx[i])lx[i]-=dis; } for(int i=0;i<ny;i++){ if(sy[i])ly[i]+=dis; else slack[i]-=dis; } } } int sum=0; for(int i=0;i<ny;i++){ if(match[i]>=0)sum+=w[match[i]][i]; }return sum;}