1 #include<cstdio>  2 #include<iostream>  3 #include<cstring>  4 #include<cstdlib>  5 #include<cmath>  6 #include<algorithm>  7 #include<string>  8 #include<map>  9 #include<set> 10 #include<vector> 11 #include<queue> 12 #include<stack> 13 #include<ctime> 14 #define M0(x)  memset(x, 0, sizeof(x)) 15 #define Inf 0x3fffffff 16 #define N 700 17 #define M 201000 18 using namespace std; 19 struct edge{ 20      int v, f, c, next; 21      edge(){} 22      edge(int _v, int _f, int _c, int _next):v(_v), f(_f), c(_c), next(_next){} 23 }; 24 struct Costflow{ 25      int last[N], pre[N], dis[N], vis[N]; 26      int tot, S, T; 27      edge e[M]; 28      void add(int u, int v, int f, int c){ 29           e[tot] = edge(v, f, c, last[u]); last[u] = tot++; 30           e[tot] = edge(u, 0, -c, last[v]); last[v] = tot++;  31      } 32      void init(int S, int T){ 33           this->S = S, this->T = T; 34           memset(last, -1, sizeof(last)); 35           tot = 0;      36      } 37      int spfa(){ 38           for (int i = 0; i <= T; ++i) 39               dis[i] = Inf; 40           memset(vis, 0, sizeof(vis)); 41           memset(pre, -1, sizeof(pre)); 42           dis[S] = 0; 43           queue<int> q; 44           q.push(S) , vis[S] = 1; 45           int p, u, v; 46           while (!q.empty()){ 47                 p = last[u = q.front()]; 48                 for ( ; p > -1; p = e[p].next){ 49                        v = e[p].v; 50                        if (dis[u] + e[p].c < dis[v] && e[p].f > 0){ 51                              dis[v] = dis[u] + e[p].c; 52                              pre[v] = p; 53                              if (!vis[v]) vis[v] = 1, q.push(v); 54                        }    55                 } 56                 vis[u] = 0; 57                 q.pop();     58           } 59           return dis[T] < Inf;   60      } 61      int costflow(){ 62           int cost = 0, flow = 0; 63           while (spfa()){ 64                int f = Inf; 65                for (int p = pre[T]; p != -1; p = pre[e[p^1].v]) 66                       f = min(f, e[p].f); 67                flow += f; 68                cost += f * dis[T]; 69                for (int p = pre[T]; p != -1; p = pre[e[p^1].v]) 70                       e[p].f -= f, e[p^1].f += f;      71           } 72           return cost; 73      } 74      /***********/  75 } F; 76 int n, m; 77 int t[70][70]; 78  79 void init(){ 80      for (int j = 1; j <= m; ++j) 81         for (int i = 1; i <= n; ++i) 82           scanf("%d", &t[i][j]);      83 } 84  85 void solve(){ 86     int S = 0, T = n * m + m + 1; 87     F.init(S, T); 88     int cnt = n * m; 89     for (int i = cnt + 1; i <= cnt + m; ++i) 90          F.add(i, T, 1, 0); 91     int cur = 0; 92     for (int i = 1; i <= n; ++i) 93        for (int j = 1; j <= m; ++j){ 94             ++cur; 95             F.add(S, cur, 1, 0); 96             for (int k = 1; k <= m; ++k) 97                 F.add(cur, cnt + k, 1, j * t[i][k]);     98        } 99     double ans = F.costflow();100     printf("%.2f\n",ans / m);101 }102 103 int main(){104 //    freopen("a.in", "r", stdin);105 //    freopen("a.out", "w", stdout);106     while (scanf("%d%d", &n, &m) != EOF){107           init();108           solve();109     }110 }