首页 > 代码库 > poj 3686 The Windy's 二分图最小权和匹配KM
poj 3686 The Windy's 二分图最小权和匹配KM
题意:
给n个玩具和m家工厂,每个玩具只能在一家工厂加工,给出每个玩具在每家工厂需要的加工时间,求这n个玩具完成时间平均值的最小值。
分析:
求最小和容易联系到二分图的最小权和匹配,这题的问题是n与m的大小关系是不确定的,也是就是说可能会有多个玩具到同一家工厂里加工的情况,这似乎与匹配的定义相矛盾。但仔细一想,如果多个玩具在同一工厂加工,他们的完成时间肯定是不一样的,所以讲w[i][j]=z 拆成w[i][0*m+j]=z,w[i][1*m+j]=2*z,w[i][2*m+j]=3*z.....再求最小权和匹配就可以了。
代码:
//poj 3686 //sep9 #include <iostream> using namespace std; const int maxN=52; int w[maxN][maxN*maxN]; int lx[maxN],ly[maxN*maxN],linky[maxN*maxN]; int visx[maxN],visy[maxN*maxN]; int slack[maxN*maxN]; int nx,ny; bool find(int x) { visx[x]=true; for(int y=0;y<ny;++y){ if(visy[y]) continue; int t=lx[x]+ly[y]-w[x][y]; if(t==0){ visy[y]=true; if(linky[y]==-1||find(linky[y])){ linky[y]=x; return true; } } else if(slack[y]>t) slack[y]=t; } return false; } int KM() { int i,j; memset(linky,-1,sizeof(linky)); memset(ly,0,sizeof(ly)); for(i=0;i<nx;++i) for(j=0,lx[i]=INT_MIN;j<ny;++j) if(w[i][j]>lx[i]) lx[i]=w[i][j]; for(int x=0;x<nx;++x){ for(i=0;i<ny;++i) slack[i]=INT_MAX; while(1){ memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(find(x)) break; int d=INT_MAX; for(i=0;i<ny;++i) if(!visy[i]&&slack[i]<d) d=slack[i]; if(d==INT_MAX) return -1; for(i=0;i<nx;++i) if(visx[i]) lx[i]-=d; for(i=0;i<ny;++i) if(visy[i]) ly[i]+=d; else slack[i]-=d; } } int result=0; for(i=0;i<ny;++i) if(linky[i]>-1) result+=w[linky[i]][i]; return result; } int main() { int cases; scanf("%d",&cases); while(cases--){ int n,m,i,j,k; scanf("%d%d",&n,&m); for(i=0;i<n;++i) for(j=0;j<m;++j){ int z; scanf("%d",&z); for(k=0;k<n;++k){ w[i][k*m+j]=z*(k+1); w[i][k*m+j]=-w[i][k*m+j]; } } nx=n,ny=n*m; printf("%.6lf\n",-KM()*1.0/n); } return 0; }
poj 3686 The Windy's 二分图最小权和匹配KM
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。