| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 3791 | Accepted: 1631 |
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 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
Source
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <vector> 7 8 using namespace std; 9 10 const int MAX = 60; 11 const int INF = 1e9 + 7; 12 int N, M; 13 int z[MAX][MAX]; 14 struct Edge {int from, to, cap, flow, cost;}; 15 vector<Edge> edges; 16 vector<int> G[MAX * MAX * MAX + 3 * MAX]; 17 int p[MAX * MAX * MAX + 3 * MAX], a[MAX * MAX * MAX + 3 * MAX]; 18 int d[MAX * MAX * MAX + 3 * MAX]; 19 bool inq[MAX * MAX * MAX + 3 * MAX]; 20 21 void add_edge(int from, int to, int cap, int cost) { 22 edges.push_back(Edge {from, to, cap, 0, cost}); 23 edges.push_back(Edge {to, from, 0, 0, -cost}); 24 int m = edges.size(); 25 G[from].push_back(m - 2); 26 G[to].push_back(m - 1); 27 } 28 29 bool bellmanford(int s, int t, int &flow, int &cost) { 30 for(int i = s; i <= t; ++i) { 31 d[i] = INF; 32 } 33 34 memset(inq, 0, sizeof(inq)); 35 d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; 36 37 queue<int> Q; 38 Q.push(s); 39 while(!Q.empty()) { 40 //printf("fuck "); 41 int u = Q.front(); Q.pop(); 42 inq[u] = 0; 43 for(int i = 0; i < G[u].size(); ++i) { 44 Edge& e = edges[ G[u][i] ]; 45 if(e.cap > e.flow && d[e.to] > d[u] + e.cost) { 46 d[e.to] = d[u] + e.cost; 47 p[e.to] = G[u][i]; 48 a[e.to] = min(a[u], e.cap - e.flow); 49 if(!inq[e.to]) { 50 inq[e.to] = 1; 51 Q.push(e.to); 52 } 53 } 54 } 55 } 56 57 if(d[t] == INF) return 0; 58 flow += a[t]; 59 cost += d[t] * a[t]; 60 61 int u = t; 62 while(u != s) { 63 edges[p[u]].flow += a[t]; 64 edges[p[u] ^ 1].flow -= a[t]; 65 u = edges[p[u]].from; 66 } 67 68 return 1; 69 } 70 71 int Mincost(int s, int t) { 72 int flow = 0, cost = 0; 73 while(bellmanford(s, t, flow, cost)); 74 return cost; 75 } 76 77 int main() 78 { 79 //freopen("sw.in", "r", stdin); 80 int t; 81 scanf("%d", &t); 82 while(t--) { 83 scanf("%d%d", &N, &M); 84 for(int i = 1; i <= N; ++i) { 85 for(int j = 1; j <= M; ++j) { 86 scanf("%d", &z[i][j]); 87 //printf("%d ", z[i][j]); 88 } 89 } 90 91 int s = 0, t = N + N * M + 1; 92 for(int i = s; i <= t; ++i) G[i].clear(); 93 edges.clear(); 94 95 for(int i = 1; i <= N; ++i) { 96 add_edge(s, i, 1, 0); 97 } 98 99 100 for(int j = 1; j <= M; ++j) { 101 for(int k = 1; k <= N; ++k) { 102 add_edge(j * N + k, t, 1, 0); 103 for(int i = 1; i <= N; ++i) { 104 add_edge(i, j * N + k, 1, z[i][j] * k); 105 } 106 } 107 } 108 printf("%.6f ", (double) Mincost(s, t) / N); 109 110 111 } 112 113 //cout << "Hello world!" << endl; 114 return 0; 115 }