好贷网好贷款

hdu2255 奔小康赚大钱 (KM)

发布时间:2016-12-5 12:34:20 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu2255 奔小康赚大钱 (KM)",主要涉及到hdu2255 奔小康赚大钱 (KM)方面的内容,对于hdu2255 奔小康赚大钱 (KM)感兴趣的同学可以参考一下。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2255 题解:KM模版题。 #include <stdio.h> #include <string.h> #define INF 0x3f3f3f3f #define MAXN 302 int w[MAXN][MAXN],match[MAXN],n; int lx[MAXN],ly[MAXN],slack[MAXN]; int visitx[MAXN],visity[MAXN]; int Scan() { char ch; int ret=0; while((ch=getchar())<'0'||ch>'9'); while(ch>='0'&&ch<='9') { ret=ret*10+(ch-'0'); ch=getchar(); } return ret; } int find(int x)//匈牙利算法 { int i,temp; visitx[x]=1; for(i=0;i<n;++i) { if(visity[i]) continue; temp=lx[x]+ly[i]-w[x][i]; if(temp==0) { visity[i]=1; if(match[i]==-1||find(match[i])) { match[i]=x; return 1;//找到增广轨 } } else { //不在相等子图中slack 取最小的 slack[i]=slack[i]>temp?temp:slack[i]; } } return 0; } void KM() { int i,j,d; memset(ly,0,sizeof(ly)); memset(match,-1,sizeof(match)); for(i=0;i<n;++i) { lx[i]=0; for(j=0;j<n;++j)//lx初始化为与它关联边中最大的 if(w[i][j]>lx[i]) lx[i]=w[i][j]; } for(i=0;i<n;++i)//对n个点匹配 { for(j=0;j<n;++j) slack[j]=INF; while(1) { memset(visitx,0,sizeof(visitx)); memset(visity,0,sizeof(visity)); if(find(i))//若成功(找到了增广轨),则该点增广完成,进入下一个点的增广 break;//若失败(没有找到增广轨),则需要改变一些点的标号,使得图中可行边的数量增加 //方法为:将所有在增广轨中(就是在增广过程中遍历到)的X方点的标号全部减去一个常数 //所有在增广轨中的Y方点的标号全部加上一个常数d d=INF; for(j=0;j<n;++j) { if(!visity[j]&&d>slack[j]) d=slack[j]; } for(j=0;j<n;++j) { if(visitx[j]) lx[j]-=d; if(visity[j])//修改顶标后,要把所有不在交错树中的Y顶点的slack值都减去d ly[j]+=d; else slack[j]-=d; } } } } int main() { int i,j,ans; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;++i) { for(j=0;j<n;++j) //scanf("%d",&w[i][j]); w[i][j]=Scan(); } KM(); ans=0; for(i=0;i<n;++i) { if(match[i]!=-1) ans+=w[match[i]][i]; } printf("%d\n",ans); } return 0; }

上一篇:Bitmap.createBitmap函数用法
下一篇:一个非常有用的函数——COALESCE

相关文章

相关评论