KM，解決最大權(quán)匹配問(wèn)題。最小權(quán)匹配的辦法是用一個(gè)很大的數(shù)-當(dāng)前邊權(quán)值，而不是直接對(duì)邊權(quán)取反(這樣只能處理左右點(diǎn)相等的完全二分圖，即K(n, n)).
HDU2426 Interesting Housing Problem
http://acm.hdu.edu.cn/showproblem.php?pid=2426
給出n個(gè)人對(duì)m個(gè)房間的喜歡度，求總喜歡度最大的匹配。赤裸裸KM求最大權(quán)，本題無(wú)視負(fù)權(quán)。
#include<iostream>
using namespace std;
#define Max(a,b) (a)>(b) ? (a) : (b)
#define Min(a,b) (a)<(b) ? (a) : (b)
const int INF=0x7f7f7f7f;
const int MAXN=501;
int n,m,e,res;
int w[MAXN][MAXN];
int mat[MAXN],slack[MAXN];
int lx[MAXN],ly[MAXN],vx[MAXN],vy[MAXN];
bool dfs(int u)
{
int v,t;
vx[u]=1;
for(v=0;v<m;++v)
{
if(!vy[v])
{
t=lx[u]+ly[v]-w[u][v];
if(t==0)
{
vy[v]=1;
if(mat[v]==-1||dfs(mat[v]))
{
mat[v]=u;return true;
}
}
else slack[v]=Min(slack[v],t);
}
}
return false;
}
bool km()
{
memset(mat,-1,sizeof(mat));
memset(ly,0,m*sizeof(ly[0]));
for(int i=0;i<n;++i)
{
lx[i]=-INF;
for(int j=0;j<m;++j) lx[i]=Max(lx[i],w[i][j]);
if(lx[i]==-INF) return false;
}
for(int i=0;i<n;++i)
{
memset(slack,127,m*sizeof(slack[0]));
while(true)
{
memset(vx,0,n*sizeof(vx[0]));
memset(vy,0,m*sizeof(vy[0]));
if(dfs(i)) break;
int d=INF;
for(int j=0;j<m;++j) if(!vy[j]) d=Min(slack[j],d);
for(int j=0;j<n;++j) if(vx[j]) lx[j]-=d;
for(int j=0;j<m;++j) if(vy[j]) ly[j]+=d;
}
}
int cnt=res=0;
for(int i=0;i<m;++i)
if(mat[i]!=-1&&w[mat[i]][i]!=-INF) res+=w[mat[i]][i],cnt++;
if(cnt==n) return true;
return false;
}
int main()
{
bool flag;
int s,r,v,len,tmp,num=0;
while(scanf("%d%d%d",&n,&m,&e)!=EOF)
{
flag=true;
if(n>m)
{
flag=false;
for(int i=0;i<e;++i) scanf("%d%d%d",&s,&r,&v);
}
else
{
for(int i=0;i<n;++i)
for(int j=0;j<m;++j) w[i][j]=-INF;
for(int i=0;i<e;++i)
{
scanf("%d%d%d",&s,&r,&v);
if(v>=0) w[s][r]=v;
}
flag=km();
}
printf("Case %d: ",++num);
if(!flag) printf("-1\n");
else printf("%d\n",res);
}
return 0;
}另種模板
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 505
#define inf 2000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)
int mat[MAXN][MAXN],n,m,match1[MAXN], match2[MAXN];
bool map[MAXN][MAXN];
int kuhn_munkras(int n, int m){
int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i<m;i++)
for (l1[i]=-inf,j=0;j<n;j++)
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
for (i=0;i<n;l2[i++]=0);
for (_clr(match1),_clr(match2),i=0;i<m;i++){
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j<n&&match1[i]<0;j++)
if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]<0){
for (i--,p=inf,k=0;k<=q;k++)
for (j=0;j<n;j++)
if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
for (k=0;k<=q;l1[s[k++]]-=p);
}
}
for (i=0;i<m;i++)
ret+=mat[i][match1[i]];
return ret;
}
bool DEBUG=false;
int main()
{
int t,x,y,len,i,j,k,ans,id=0;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
for(i=0;i<n;i++)for(j=0;j<m;j++)mat[i][j]=-inf;
memset(map,false,sizeof(map));
while(k--)
{
scanf("%d%d%d",&x,&y,&len);
if(len<0)continue;
mat[x][y]=len;
map[x][y]=true;
}
printf("Case %d: ",++id);
if(n>m)
{
printf("-1\n");
continue;
}
ans=kuhn_munkras(m,n);
for(i=0;i<n;i++)if(!map[i][match1[i]])break;
printf("%d\n",i==n?ans:-1);
}
return 0;
}
PKU2195 Going Home
http://acm.pku.edu.cn/JudgeOnline/problem?id=2195
求最小權(quán)匹配，先將權(quán)值取反然后算最大權(quán)匹配。
#include<iostream>
#include<cmath>
using namespace std;
#define Max(a,b) (a)>(b) ? (a) : (b)
#define Min(a,b) (a)<(b) ? (a) : (b)
typedef struct Node
{
int x,y;
}MH;
const int INF=0x7f7f7f7f;
const int MAXN=101;
char map[MAXN][MAXN];
MH M[MAXN],H[MAXN];
int n,res;
int w[MAXN][MAXN];
int mat[MAXN],vx[MAXN],vy[MAXN],lx[MAXN],ly[MAXN],slack[MAXN];
bool dfs(int u)
{
int v,t;
vx[u]=1;
for(v=0;v<n;++v)
{
t=lx[u]+ly[v]-w[u][v];
if(!vy[v]&&t==0)
{
vy[v]=1;
if(mat[v]==-1||dfs(mat[v]))
{
mat[v]=u;
return true;
}
}
else slack[v]=Min(slack[v],t);
}
return false;
}
void KM()
{
memset(mat,-1,n*sizeof(mat[0]));
memset(ly,0,n*sizeof(ly[0]));
for(int i=0;i<n;++i)
{
lx[i]=-INF;
for(int j=0;j<n;++j) lx[i]=Max(lx[i],w[i][j]);
}
for(int i=0;i<n;++i)
{
memset(slack,127,n*sizeof(slack[0]));
while(true)
{
memset(vx,0,n*sizeof(vx[0]));
memset(vy,0,n*sizeof(vy[0]));
if(dfs(i)) break;
int d=INF;
for(int j=0;j<n;++j) if(!vy[j]) d=Min(d,slack[j]);
for(int j=0;j<n;++j)
{
if(vx[j]) lx[j]-=d;
if(vy[j]) ly[j]+=d;
}
}
}
res=0;
for(int i=0;i<n;++i) res+=w[mat[i]][i];
}
int main()
{
int a,b,n1,n2;
while(scanf("%d%d",&a,&b)&&a&&b)
{
n1=n2=0;
for(int i=0;i<a;++i)
{
scanf("%s",map[i]);
for(int j=0;j<b;++j)
{
if(map[i][j]=='m') M[n1].x=i,M[n1++].y=j;
if(map[i][j]=='H') H[n2].x=i,H[n2++].y=j;
}
}
n=n1;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
w[i][j]=-(abs(H[i].x-M[j].x)+abs(H[i].y-M[j].y));
KM();
printf("%d\n",-res);
}
return 0;
}