gistfile1.cpp

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <functional>
#include <utility>
#include <vector>
#include <list>
#include <queue>

using namespace std;

const int N = 1024;
bool vis[N];
double pot[N];

struct Edge {
  int a, b;
  double cost;
  int backward, forward;
  Edge(int a, int b, double cost, int cap) :a(a), b(b), cost(cost),
    backward(cap), forward(1) {}
  int other(int x) { return x == a ? b : a; }
  double cost_from(int x) { return x == a ? forward*cost : -backward*cost; }
  double red_cost_from(int x) {
    return cost - pot[x] + pot[other(x)];
  }
  int flow_from(int x) { return x == a ? forward : backward; }
  int cap_from(int x) { return x == a ? backward : forward; }
  void add_flow(int x, int flow) {
    if (x == a) {
      forward += flow;
      backward -= flow;
    } else {
      forward -= flow;
      backward += flow;
    }
  }
};

struct Node {
  int v, amt;
  Edge *pred;
  double d;
  Node() {}
  Node(int v, Edge* pred, int amt, double d) : v(v), pred(pred), amt(amt), d(d) {}
  bool operator<(const Node& o) const {
    return d > o.d;
  }
};

typedef list<Edge*> EdgeList;
typedef vector<EdgeList> AdjList;

#define FOR_EDGE(adj,v,it) for (EdgeList::iterator it = adj[v].begin(); \
    it != adj[v].end(); ++it)

AdjList adj;
vector<Edge> edges;
double dists[N];

// reduce costs using bellman-ford
void reduce_bf(int s) {
  fill(dists, dists+N, -1);
  memset(vis, 0, sizeof(vis));
  deque<int> q;
  q.push_back(s);
  dists[s] = 0;
  while (q.size()) {
    int curr = q.front();
    q.pop_front();
    vis[curr] = false;
    FOR_EDGE(adj, curr, it) {
      Edge *e = *it;
      int o = e->other(curr);
      if (o == e->a) continue;
      if (dists[o] == -1 || dists[s] + e->cost < dists[o]) {
        dists[o] = dists[s] + e->cost;
        if (!vis[o]) {
          vis[o] = true;
          if (dists[q.front()] > dists[o]) {
            q.push_front(o);
          } else {
            q.push_back(o);
          }
        }
      }
    }
  }
  // now reduce costs. assumption: graph is connected
  for (int i = 0; i < N; ++i) {
    pot[i] = -dists[i];
  }
}

Edge *preds[N];
int amt[N]; // flow amount

void flow(int t) {
  int curr = t;
  for (Edge *e = preds[t]; e != NULL; ) {
    int o = e->other(curr);
    e->add_flow(o, amt[t]);
    e = preds[curr];
    curr = o;
  }
}

// reduce costs using dijsktra's algorithm
bool reduce_dijkstra(int s, int t) {
  puts("yo");
  fill(dists, dists+N, -1);
  memset(preds, 0, sizeof(preds));
  priority_queue<Node> pq;
  pq.push(Node(s, NULL, 1 << 29, 0));
  while (pq.size()) {
    Node curr = pq.top();
    pq.pop();
    int v = curr.v;
    double d = curr.d;
    if (dists[v] != -1 && dists[v] < d) continue;
    printf("%d %f\n", v, d);
    dists[v] = d;
    preds[v] = curr.pred;
    amt[v] = curr.amt;
    if (v == t) break;
    FOR_EDGE(adj, v, it) {
      Edge *e = *it;
      if (e->cap_from(v) == 0) continue;
      int o = e->other(v);
      if (dists[o] == -1 || dists[o] > d + e->red_cost_from(v)) {
        pq.push(Node(o, e, min(amt[v], e->cap_from(v)),
              d + e->red_cost_from(v)));
      }
    }
  }
  puts("yooo");
  if (dists[t] != -1) {
    for (int i = 0; i < N; ++i) {
      pot[i] -= dists[i] >= 0 ? dists[i] : dists[t];
    }
    return true;
  } else return false;
}

void ssp(int s, int t) {
  memset(pot, 0, sizeof(pot));
  reduce_bf(s); // not needed if costs are nonnegative
  while (reduce_dijkstra(s, t)) flow(t);
}

int main() {
 
  int n, m;
  while (scanf("%d%d", &n, &m) == 2 && (n || m)) {
    // source = 0, sink = n+m+1
    adj.clear();
    adj.resize(n+m+2);
    edges.clear();
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        double cost;
        scanf("%lf", &cost);
        edges.push_back(Edge(1 + i, n + 1 + j, cost, 1));
        edges.push_back(Edge(0, 1+i, 0, 1));
        edges.push_back(Edge(n+1+j, n+m+1, 0, 1));
      }
    }
    for (int i = 0; i < edges.size(); ++i) {
      Edge &e = edges[i];
      adj[e.a].push_back(&e);
      adj[e.b].push_back(&e);
    }

    ssp(0, n+m+1);

    double cost = 0;
    for (int i = 0; i < edges.size(); ++i) {
      Edge &e = edges[i];
      cost += e.cost_from(e.a);
    }
    printf("%.2f\n", cost/n);
  }

  return 0;
}