Problem G

Crime Wave – The Sequel

Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

n banks have been robbed this fine day. m (greater than or equal to n) police cruisers are on duty at various locations in the city. n of the cruisers should be dispatched, one to each of the banks, so as to minimize the average time of arrival at the n banks.

Input

The input file contains several sets of inputs. The description of each set is given below:

The first line of input contains 0 < n <= m <= 20. n lines follow, each containing m positive real numbers: the travel time for cruiser m to reach bank n.

Input is terminated by a case where m=n=0. This case should not be processed.  

Output

For each set of input output a single number: the minimum average travel time, accurate to 2 fractional digits.

Sample Input                             Output for Sample Input

3 4

10.0 23.0 30.0 40.0

5.0 20.0 10.0 60.0

18.0 20.0 20.0 30.0

Problemsetter: Gordon Cormack, EPS

1 1
0.015

無法輸出 0.02

#include <stdio.h>
#include <string.h>
#include <math.h>
#define eps 1e-6
double W[105][105];
int N, M;
int mx[105], my[105]; // match arr
double lx[105], ly[105]; // label arr
int x[105], y[105]; // used arr
int hungary(int nd) {
    int i;
    x[nd] = 1;
    for(i = 1; i <= M; i++) {
        if(y[i] == 0 && fabs(W[nd][i]-lx[nd]-ly[i]) < eps) {
            y[i] = 1;
            if(my[i] == 0 || hungary(my[i])) {
                my[i] = nd;
                return 1;
            }
        }
    }
    return 0;
}
double KM() {
    int i, j, k;
    double d;
    memset(mx, 0, sizeof(mx));
    memset(my, 0, sizeof(my));
    memset(lx, 0, sizeof(lx));
    memset(ly, 0, sizeof(ly));
    for(i = 1; i <= N; i++)
        for(j = 1, lx[i] = W[i][j]; j <= M; j++)
            lx[i] = lx[i] > W[i][j] ? lx[i] : W[i][j];
    for(i = 1; i <= N; i++) {
        while(1) {
            memset(x, 0, sizeof(x));
            memset(y, 0, sizeof(y));
            if(hungary(i))  break;
            d = 0xfffffff;
            for(j = 1; j <= N; j++) {
                if(x[j]) {
                    for(k = 1; k <= M; k++)
                        if(!y[k])
                        d = d < lx[j]+ly[k]-W[j][k] ?
                            d : lx[j]+ly[k]-W[j][k];
                }
            }
            if(d == 0xfffffff)  break;
            for(j = 1; j <= N; j++)
                if(x[j])    lx[j] -= d;
            for(j = 1; j <= M; j++)
                if(y[j])    ly[j] += d;
        }
    }
    double res = 0;
    for(i = 1; i <= M; i++) {
        if(my[i])
            res += W[my[i]][i];
    }
    return res;
}
int main() {
    int n, m;
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 0 && m == 0)
            break;
        N = n, M = m;
        int i, j;
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                scanf("%lf", &W[i][j]);
                W[i][j] *= -1;
            }
        }
        printf("%.2lf\n", -KM()/n+eps);
    }
    return 0;
}
/*
1 1
0.015
*/