@KirinBill
2017-11-12T20:14:26.000000Z
字数 4888
阅读 2071
学习笔记
二分图
目录
对于一个有完美匹配的二分图,将其中的边都赋了一个边权(可以为负),其中边权和最大的完美匹配叫做该二分图的最佳完美匹配。
一些约定:
定理:
int n;
int G[MAXN][MAXN],lx[MAXN],ly[MAXN],slack[MAXN],match[MAXN];
bool visx[MAXN],visy[MAXN];
bool Hungary(int x){
visx[x]=true;
for(int y=1,dta;y<=n;++y){
dta=lx[x]+ly[y]-G[x][y];
if(!visy[y] && dta==0){
visy[y]=true;
if(!match[y] || Hungary(match[y])){
match[y]=x;
return true;
}
}
else slack[y]=min(slack[y],dta);
}
return false;
}
inline int KM(){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
lx[i]=max(lx[i],G[i][j]);
}
for(int x=1,d;x<=n;++x){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
memset(slack,0x7f,sizeof(slack));
while(!Hungary(x)){
d=INT_MAX;
for(int y=1;y<=n;++y){
if(!visy[y]) d=min(d,slack[y]);
}
for(int i=1;i<=n;++i){
if(visx[i]){
lx[i]-=d;
visx[i]=false;
}
if(visy[i]){
ly[i]+=d;
visy[i]=false;
}
}
}
}
int ret=0;
for(int i=1;i<=n;++i)
ret+=lx[i]+ly[i];
return ret;
}
代码:
#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>
using std::min;
using std::max;
const int MAXN=305;
int n;
int lx[MAXN],ly[MAXN],G[MAXN][MAXN],slack[MAXN],match[MAXN];
bool visx[MAXN],visy[MAXN];
bool Hungary(int x){
visx[x]=true;
for(int y=1,dta;y<=n;++y){
dta=lx[x]+ly[y]-G[x][y];
if(!visy[y] && dta==0){
visy[y]=true;
if(!match[y] || Hungary(match[y])){
match[y]=x;
return true;
}
}
else slack[y]=min(slack[y],dta);
}
return false;
}
inline int KM(){
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
memset(match,0,sizeof(match));
for(int x=1;x<=n;++x){
for(int y=1;y<=n;++y)
lx[x]=max(lx[x],G[x][y]);
}
for(int x=1,d;x<=n;++x){
memset(slack,0x7f,sizeof(slack));
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
while(!Hungary(x)){
d=INT_MAX;
for(int y=1;y<=n;++y){
if(!visy[y]) d=min(d,slack[y]);
}
for(int i=1;i<=n;++i){
if(visx[i]){
lx[i]-=d;
visx[i]=false;
}
if(visy[i]){
ly[i]+=d;
visy[i]=false;
}
}
}
}
int ret=0;
for(int i=1;i<=n;++i)
ret+=lx[i]+ly[i];
return ret;
}
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
scanf("%d",&G[i][j]);
}
printf("%d\n",KM());
}
return 0;
}
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using std::min;
using std::max;
const int MAXN=505;
int n;
int G[MAXN][MAXN],lx[MAXN],ly[MAXN],slack[MAXN],match[MAXN];
bool visx[MAXN],visy[MAXN];
bool Hungary(int x){
visx[x]=true;
for(int y=1,dta;y<=n;++y){
dta=lx[x]+ly[y]-G[x][y];
if(!visy[y] && dta==0){
visy[y]=true;
if(!match[y] || Hungary(match[y])){
match[y]=x;
return true;
}
}
else slack[y]=min(slack[y],dta);
}
return false;
}
inline int KM(){
memset(lx,-0x7f,sizeof(lx));
memset(ly,0,sizeof(ly));
memset(match,0,sizeof(match));
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
lx[i]=max(lx[i],G[i][j]);
}
for(int x=1,d;x<=n;++x){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
memset(slack,0x7f,sizeof(slack));
while(!Hungary(x)){
d=INT_MAX;
for(int y=1;y<=n;++y){
if(!visy[y]) d=min(d,slack[y]);
}
for(int i=1;i<=n;++i){
if(visx[i]){
lx[i]-=d;
visx[i]=false;
}
if(visy[i]){
ly[i]+=d;
visy[i]=false;
}
}
}
}
int ret=0;
for(int i=1;i<=n;++i)
ret+=lx[i]+ly[i];
return ret;
}
int main(){
int ans;
while(scanf("%d",&n)!=EOF){
memset(G,0,sizeof(G));
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
scanf("%d",&G[i][j]);
}
ans=KM();
for(int i=1;i<=n;++i)
printf("%d ",lx[i]);
putchar('\n');
for(int i=1;i<=n;++i)
printf("%d ",ly[i]);
putchar('\n');
printf("%d\n",ans);
}
return 0;
}