HDU - 2255 奔小康赚大钱(二分图最大权匹配+KM)

题目链接：点击查看

题目大意：中文题目，简单来说就是n个人和n个房子最大匹配，需要一一对应并且满足权值和最大

题目分析：二分图的完备匹配，条件完全符合KM算法的局限性，直接套模板即可，后续学习费用流（如果能学会的话）会来更新费用流的写法的

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=310;int n;int la[N],lb[N];//顶标bool visa[N],visb[N];int maze[N][N];//边权int match[N];int upd[N];bool dfs(int x) {visa[x]=true;for(int i=1;i<=n;i++){if(!visb[i]){if(la[x]+lb[i]-maze[x][i]==0){visb[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}elseupd[i]=min(upd[i],la[x]+lb[i]-maze[x][i]);}}return false; } int KM() {memset(match,0,sizeof(match));for(int i=1;i<=n;i++){la[i]=-inf;lb[i]=0;for(int j=1;j<=n;j++)la[i]=max(la[i],maze[i][j]);}for(int i=1;i<=n;i++){while(1){memset(visa,false,sizeof(visa));memset(visb,false,sizeof(visb));memset(upd,inf,sizeof(upd));if(dfs(i))break;int delta=inf;for(int j=1;j<=n;j++)if(!visb[j])delta=min(delta,upd[j]);for(int j=1;j<=n;j++){if(visa[j])la[j]-=delta;if(visb[j])lb[j]+=delta;}}}int ans=0;for(int i=1;i<=n;i++)ans+=maze[match[i]][i];return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&maze[i][j]);printf("%d\n",KM());}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU - 2255 奔小康赚大钱(二分图最大权匹配+KM)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。