1070: [SCOI2007]修车
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 6209 Solved: 2641
[Submit][Status][Discuss]
Description
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同
的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最
小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
Input
第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人
员维修第i辆车需要用的时间T。
Output
最小平均等待时间，答案精确到小数点后2位。
Sample Input
2 2
3 2
1 4
3 2
1 4
Sample Output
1.50
HINT
数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)
我们先将所有m拆成n个点，每个点表示m倒数第i个维修的车。
对于每一辆车，我们向所有m拆的点连边，容量为1，费用为cost[i][j]*i表示他花的时间和后i个人等待的时间和。
跑最小费用最大流。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define maxn 700
using namespace std;
int n,m;
int a[][];
int t;
bool vis[maxn];
int dis[maxn];
struct data {
int to,next,c,w;
}e[maxn*maxn];
int head[maxn],cnt;
int q[maxn];
void add(int u,int v,int w,int c){e[cnt].next=head[u];e[cnt].to=v;e[cnt].c=c;e[cnt].w=w;head[u]=cnt++;}
int use=;
bool spfa() {
for(int i=;i<=t;i++) dis[i]=-;
memset(vis,,sizeof(vis));
int h=,tail=;
q[]=t;
dis[t]=;
vis[t]=;
while(h!=tail) {
int now=q[h++];if(h==maxn) h=;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(e[i^].w>&&dis[to]<dis[now]+e[i].c) {
dis[to]=dis[now]+e[i].c;
if(!vis[to]){
vis[to]=;
q[tail++]=to;if(tail==maxn) tail=;
}
}
}
vis[now]=;
}
use-=dis[];
return dis[]!=-;
}
int ans=;
int dfs(int now,int af) {
if(now==t||af==){ans+=use*af;return af;}
vis[now]=;
int flow=,f=;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(vis[to]) continue;
if(dis[to]==dis[now]+e[i].c&&e[i].w>&&(f=dfs(to,min(af,e[i].w)))) {
e[i].w-=f;
e[i^].w+=f;
flow+=f;
af-=f;
if(!af) break;
}
}
return flow;
}
void zkw() {
while(spfa()) {
do {
memset(vis,,sizeof(vis));
}while(dfs(,));
memset(vis,,sizeof(vis));
use=;
}
}
int main() {
memset(head,-,sizeof(head));
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=;i<=n;i++) {add(,i,,);add(i,,,);}
t=;
for(int i=n+;i<=n+n*m;i++) {add(i,t,,);add(t,i,,);}
for(int i=;i<=n;i++) {
for(int j=n+;j<=n+n*m;j++){
int cost=j-n;
int temp=cost/n+;
cost%=n;
if(!cost) cost=n,temp--;
add(i,j,,a[i][temp]*cost);
add(j,i,,-a[i][temp]*cost);
}
}
zkw();
double ans1;
ans1=(double)ans/(double)n;
printf("%.2lf",ans1);
}