最大权值匹配，建图不好想，假设某个机器处理了k个玩具，时间分别为a1,a2…..,ak
那么该机器耗费的时间为a1+a1+a2+a1+a2+a3.......a1+a2+...ak??
即a1*k + a2 * (k - 1) + a3 * (k - 2).... + ak
ak玩具在某个机器上倒数第k个处理，所耗费全局的时间为ak*k
对每个机器，最多可以处理n个玩具，拆成n个点，1~n分别代表某个玩具在这个机器上倒数第几个被加工的,对于每个玩具i，机器j中拆的每个点k，连接一条map[i][j]*k权值的边
[cpp]
#include
#include
#include
#include
#include
using namespace std;?
const int MAXN=5000;?
const int INF=0x7fffffff;?
int nx, ny, w[MAXN][MAXN], lx[MAXN], ly[MAXN];?
int fx[MAXN], fy[MAXN], matx[MAXN], maty[MAXN];?
int map[MAXN][MAXN];?
int n,m;?
struct node?
{?
??? int x;?
??? int y;?
}h[MAXN],man[MAXN];?
int path(int u)?
{???
??? fx[u] = 1;?
??? for (int v = 1; v <= ny; v++)??
??? if (lx[u] + ly[v] == w[u][v] && fy[v] < 0)?
??? {????
??????????? fy[v] = 1;?
??????????? if (maty[v] < 0 || path(maty[v]))?
??????????? {?????
??????????????? matx[u] = v;?????
??????????????? maty[v] = u;?????
??????????????? return 1;????
??????????? }?
???? }?
???? return 0;?
}?
int km()?
{???
??? int i,j,k,ret = 0;?
??? memset(ly, 0, sizeof(ly));?
??? for (i = 1; i <= nx; i++)?
??? {???
??????? lx[i] = -INF;?
??????? for (j = 1; j <= ny; j++)??
??????? if (w[i][j] > lx[i]) lx[i] = w[i][j];?
??? }?
??? memset(matx, -1, sizeof(matx));?
??? memset(maty, -1, sizeof(maty));?
??? for (i = 1; i <= nx; i++)?
??? {????
??????? memset(fx, -1, sizeof(fx));?
??????? memset(fy, -1, sizeof(fy));?
??????? if (!path(i))?
??????? {???
??????????? i--;????
??????????? int p = INF;?
??????????? for (k = 1; k <= nx; k++)?
??????????? {?
??????????????? if (fx[k] > 0)?
??????????????? for (j = 1; j <= ny; j++)??
??????????????? if (fy[j] < 0 && lx[k] + ly[j] - w[k][j] < p)?
??????????????? p=lx[k]+ly[j]-w[k][j];?
??????????? }?
??????????? for (j = 1; j <= ny; j++)??
??????????? ly[j] += fy[j]<0 ? 0 : p;?
??????????? for (j = 1; j <= nx; j++)??
??????????? lx[j] -= fx[j]<0 ? 0 : p;?
??????? }?
??? }?
??? for (i = 1; i <= ny; i++)?
??? {?
??????? if(maty[i]>=1)?
??????? ret += w[maty[i]][i];?
??? }?
??? return ret;?
}?
?void init()?
{?
??? int i,j,k;?
??? scanf("%d %d",&n,&m);?
??? for(i=1;i<=n;i++)?
??? for(j=1;j<=m;j++)?
??? scanf("%d",&map[i][j]);?
??? nx=n;?
??? ny=n*m;?
??? for(i=1;i<=n;i++)?
??? for(j=1;j<=m;j++)?
??? for(k=1;k<=n;k++)?
??? w[i][(j-1)*n+k]=-map[i][j]*k;?
?}?
int main()?www.2cto.com
{?
??? int t;?
??? scanf("%d",&t);?
??? while(t--)?
??? {?
??????? init();?
??????? printf("%.6f\n",-1.0*km()/n);?
??? }?
??? return 0;?
}?
?