The Windy’s

Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 6596 Accepted: 2675
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

和一道省选的修车一样的。

我们对于每一个生产工厂拆成n个，然后依次考虑每个工厂生产当前倒数第k个物品，对后面产生的影响即可。

AC代码：

#include<queue>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
const int inf=0x3f3f3f3f;
const int N=1e4+10,M=1e6+10;
using namespace std;
int T,n,m,s,t,d[N],v[N],e[N];
int head[N],nex[M],to[M],w[M],flow[M],tot;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
inline void init(){
	tot=1; memset(head,0,sizeof head); t=n*m+n+1;
}
inline int spfa(){
	memset(d,inf,sizeof d); d[s]=0; queue<int> q;	q.push(s);
	int vis[N]={0}; vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=inf;
}
int EK(){
	int res=0;
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=mi*d[t];
	}
	return res;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d %d",&n,&m);	init();
		for(int i=1;i<=n;i++){
			add(s,i,1,0);
			for(int j=1;j<=m;j++){
				int x;	scanf("%d",&x);
				for(int k=1;k<=n;k++)	add(i,j*n+k,1,x*k);
			}
		}
		for(int i=1;i<=m;i++)	for(int j=1;j<=n;j++)	add(i*n+j,t,1,0);
		printf("%.6f\n",(double)EK()/n);
	}
	return 0;
}