The Windy's

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 2846		Accepted: 1232

Description

The Windy's is a world famous toy factory that owns M top-class workshop to make toys. This year the manager receives N orders for toys. The manager knows that every order will take different amount of hours in different workshops. More precisely, the i-th order will take Z_ij hours if the toys are making in the j-th workshop. Moreover, each order's work must be wholly completed in the same workshop. And a workshop can not switch to another order until it has finished the previous one. The switch does not cost any time.

The manager wants to minimize the average of the finishing time of the N orders. Can you help him?

Input

The first line of input is the number of test case. The first line of each test case contains two integers, N and M (1 ≤ N,M ≤ 50).

The next N lines each contain M integers, describing the matrix Z_ij (1 ≤ Z_ij ≤ 100,000) There is a blank line before each test case.

Output

For each test case output the answer on a single line. The result should be rounded to six decimal places.

Sample Input

33 4100 100 100 199 99 99 198 98 98 13 41 100 100 10099 1 99 9998 98 1 983 41 100 100 1001 99 99 9998 1 98 98

Sample Output

2.0000001.0000001.333333 这题的构图还是很精妙的 注意要学会拆点

#include
     
      using namespace std;const int INF = INT_MAX;const int xmax = 55;const int ymax = 2510;int n, m;int input[xmax][xmax];int map[xmax][ymax];int sx[xmax], sy[ymax], lx[xmax], ly[ymax];int match[ymax];int dfs(int a){    sx[a]=1;    for(int i=1;i<=m;i++)    {        if(sy[i]==0 && lx[a]+ly[i]==map[a][i])        {            sy[i]=1;            if(match[i]==-1 || dfs(match[i])==1)            {                match[i]=a;                return 1;            }        }    }    return 0;}int km(){    for(int i=1;i<=n;i++)    {        lx[i]=INF;        for(int j=1;j<=m;j++)        {            if(map[i][j]>lx[i])            {                lx[i]=map[i][j];            }        }    }    memset(match, -1, sizeof(match));    memset(ly, 0, sizeof(ly));    for(int k=1;k<=n;k++)    {        while(1)        {            memset(sx, 0, sizeof(sx));            memset(sy, 0, sizeof(sy));            if(dfs(k))                break;            int dmin = INF;            for(int i=1; i<=n;i++)            {                if(sx[i])                {                    for(int j=1;j<=m;j++)                    {                        if(!sy[j])                        {                            dmin=(map[i][j]-lx[i]-ly[j])
      
       >cases;    while(cases--)    {        scanf("%d%d",&n,&m);        memset(input, 0, sizeof(input));        memset(map, 0, sizeof(map));        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                scanf("%d",&input[i][j]);            }        }        for(int s=1;s<=n;s++)            for(int i=1;i<=n;i++)                for(int j=1;j<=m;j++)                    map[s][(i-1)*m+j] = i*input[s][j];        m=n*m;        printf("%.6f\n",km()*1.0/n);    }    return 0;}