题目链接
HDU-2426
题意
有n个学生和m个公寓，并给出e个评价(si,ri,vi)。表示学生si对公寓ri的评分为vi。vi为负值表示该学生不想住这个公寓。学生只能入住自己评价过的公寓。现要求将n个学生都分配进公寓（每个人一间公寓），满足学生意愿（不住评价为负的公寓）且使得评价总分最高。
分析
将学生作为左侧顶点集，公寓作为右侧顶点集，评价作为边权值。未评价或评价为负的边权值置为负无穷大。运用KM算法求出最大权匹配即可。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;const int maxn=550;
int w[maxn][maxn],from[maxn],match[maxn];
int lx[maxn],ly[maxn],visx[maxn],visy[maxn];
int nx,ny,slack[maxn];bool Find(int u)
{visx[u]=1;for(int v=0;v<ny;v++)if(!visy[v]){//看是否是相等子图int tmp=lx[u]+ly[v]-w[u][v];if(tmp==0)//是相等子图{visy[v]=1;//匈牙利算法找增广路if(from[v]==-1 || Find(from[v])){from[v]=u;match[u]=v;return true;}}else slack[v]=min(slack[v],tmp);}return false;
}
int KM()
{//初始化可行顶标for(int i=0;i<ny;i++) ly[i]=0;for(int i=0;i<nx;i++){lx[i]=-INF;for(int j=0;j<ny;j++) lx[i]=max(lx[i],w[i][j]);}//清空匹配点memset(from,-1,sizeof(from));memset(match,-1,sizeof(match));//在相等子图中运用匈牙利算法找匹配for(int u=0;u<nx;u++){//维护slackfor(int i=0;i<ny;i++) slack[i]=INF;while(true)//循环找增广路{memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(Find(u)) break;int d=INF;for(int i=0;i<ny;i++)if(!visy[i])d=min(d,slack[i]);//修该匹配边的顶标for(int i=0;i<nx;i++)if(visx[i])lx[i]-=d;for(int i=0;i<ny;i++){if(visy[i]) ly[i]+=d;else slack[i]-=d;}}}//根据匹配输出最大权int ans=0,cnt=0;for(int i=0;i<nx;i++){if(match[i]!=-1){int val=w[i][match[i]];if(val==-INF) return -1;cnt++;ans+=val;}}if(cnt<nx) return -1;return ans;
}
int main()
{int n,m,e,kase=1;while(~scanf("%d%d%d",&n,&m,&e)){nx=n;ny=m;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++){int u,v,val;scanf("%d%d%d",&u,&v,&val);if(val>=0)w[u][v]=val;}printf("Case %d: %d\n",kase++,KM());}return 0;
}
参考博客
模板总结——二分图最大权匹配