题意：
给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;elseslack[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;
}