最大權值匹配，建圖不好想，假設某個機器處理了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<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
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;
}
