The Windy’s POJ - 3686（最小费用流）
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 Zij 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 Zij (1 ≤ Zij ≤ 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
3
3 4
100 100 100 1
99 99 99 1
98 98 98 1
3 4
1 100 100 100
99 1 99 99
98 98 1 98
3 4
1 100 100 100
1 99 99 99
98 1 98 98
Sample Output
2.000000
1.000000
1.333333
题意：
有N个订单和M个机器，给出第i个订单在第j个机器完成的时间Zij，每台机器同一时刻只能处理一个订单，机器必须完整地完成一个订单后才能接着完成下一个订单。问N个订单完成时间的平均值最少为多少？
计算时间时，把等待的时间也算进去的
题解：
对于一个工厂来说
这个式子可以理解为：对于一种玩具（有n件）而言，多个工厂依次加工，每次加工只允许一个工厂运行，所需要的总时间。
那么对于第i件玩具来说，在这个工厂花费时间为 （N-i）* Z
未知量： 玩具 工厂 这个工厂加工这个玩具是第几个加工
对于每件订单Zij（Zij包含信息 ：第i个订单在第j个机器完成的时间Zij），
每个玩具花费是时间是（N-i）* Z（费用是N-i倍价值）
匹配方法：
第i个玩具(1 <= i <= N)，与第j个工厂(j = aN + 1, a = 1, 2, 3…准确的说，aN + 1 <= j <= (a + 1)*N )的k倍时间(1 <= k <= N)匹配。
说明第k个加工的是玩具i在工厂j加工。
说明一点：k = 1， 2， 3，4， 5…N且在匹配时不会匹配到相同的k。
因为k = 1只与所有玩具的匹配一次，那么最终只有一个玩具会选择k = 1.
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
#define SZ(v) (int)v.size()
#define pii pair<int,int>const int INF = 0x3f3f3f3f;
const int MAXN = 1e4 + 10;struct MCMF {
struct Edge {
int v, cap, cost, rev;Edge(int v, int cap, int cost, int rev):v(v),cap(cap),cost(cost),rev(rev){
}};int flow, cost, s, t, n;int dist[MAXN], H[MAXN], pv[MAXN], pe[MAXN];std::vector<Edge> G[MAXN];bool dijkstra() {
std::priority_queue<pii, std::vector<pii>, std::greater<pii> > q;std::fill(dist, dist + n + 1, INF);dist[s] = 0; q.push({
0, s});while (!q.empty()) {
pii x = q.top(); q.pop();int &u = x.second;if (dist[u] < x.first) continue;for (int i = 0; i < SZ(G[u]); ++i) {
Edge &e = G[u][i];int &v = e.v;pii y(dist[u] + e.cost + H[u] - H[v], v);if (e.cap > 0 && dist[v] > y.first) {
dist[v] = y.first;pe[v] = i, pv[v] = u;q.push(y);}}}if (dist[t] == INF) return false;for (int i = 0; i <= n; ++i) H[i] += dist[i];int f = INF;for (int v = t; v != s; v = pv[v]) f = std::min(f, G[pv[v]][pe[v]].cap);flow += f;cost += f * H[t];for (int v = t; v != s; v = pv[v]) {
Edge &e = G[pv[v]][pe[v]];e.cap -= f;G[v][e.rev].cap += f;}return true;}void solve(int s, int t) {
this->s = s, this->t = t;flow = cost = 0;std::fill(H, H + n + 1, 0);while (dijkstra());}void init(int n) {
this->n = n;for (int i = 0; i <= n; ++i) G[i].clear();}void add_edge(int u, int v, int cap, int cost) {
G[u].push_back(Edge(v, cap, cost, SZ(G[v])));G[v].push_back(Edge(u, 0, -cost, SZ(G[u]) - 1));}} mcmf;int Z[55][55];int main() {
int T;cin >> T;//scanf("%d" ,&T);while(T--){
memset(Z, 0, sizeof(Z));int M, N;cin >> N >> M;//scanf("%d%d", &N, &M);for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++)cin >> Z[i][j];//scanf("%d", &Z[i][j]);}int s = N + N * M + 1, t = s + 1;mcmf.init(t);//0 ~ N 玩具//N+1 ~ N*N 工厂,第i个玩具对应j号工厂(每个工厂费用k倍(1<=k<=N))//第1个玩具对应1号工厂的时间1~N倍，对应序号N+1 ~ 2N//s到玩具for(int i = 1; i <= N; i++)mcmf.add_edge(s, i, 1, 0);//工厂到tfor(int j = 1; j <= M; j++) {
for(int k = 1; k <= N; k++) {
mcmf.add_edge(N + (j - 1) * N + k, t, 1, 0);}}//玩具到工厂for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
for(int k = 1; k <= N; k++) {
mcmf.add_edge(i, N + (j - 1) * N + k, 1, k * Z[i][j]);}}}mcmf.solve(s, t);cout << fixed << setprecision(6) << (double)mcmf.cost / (double) N << endl;//printf("%.6lf\n",ans);}
}