1070: [SCOI2007]修车
Time Limit: 1 Sec
Memory Limit: 128 MB
[
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
Sample Output
1.50
HINT
数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)
Source
太晚了，不想写题解了
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define INF 0x7fffffff
using namespace std;
const int N = 605;
int n,m,cnt=1,dis[N],q[N],last[N],S,T,ans,t[65][10];
bool mark[N];
struct Edge{
int to,next,v,c;
}e[100005];
void insert( int u, int v, int w, int c ){
e[++cnt].to = v; e[cnt].next = last[u]; last[u] = cnt; e[cnt].v = w; e[cnt].c = c;
e[++cnt].to = u; e[cnt].next = last[v]; last[v] = cnt; e[cnt].v = 0; e[cnt].c = -c;
}
bool spfa(){
memset(mark,0,sizeof(mark));
for( int i = S; i <= T; i++ ) dis[i] = INF;
int head = 0, tail = 1;
dis[T] = 0; mark[T] = 1; q[0] = T;
while( head != tail ){
int now = q[head++]; if( head == T ) head = 0;
for( int i = last[now]; i; i = e[i].next )
if( e[i^1].v && dis[e[i].to] > dis[now] - e[i].c ){
dis[e[i].to] = dis[now] - e[i].c;
if( !mark[e[i].to] ){
mark[e[i].to] = 1; q[tail++] = e[i].to; if( tail == T ) tail = 0;
}
}
mark[now] = 0;
}
return dis[S] != INF;
}
int dfs( int x, int f ){
mark[x] = 1;
int w, used = 0;
if( x == T ) return f;
for( int i = last[x]; i; i = e[i].next )
if( !mark[e[i].to] && e[i].v && dis[e[i].to] == dis[x] - e[i].c ){
w = dfs( e[i].to, min(f-used,e[i].v) );
ans += w*e[i].c; e[i].v -= w; e[i^1].v += w; used += w;
if( used == f ) return f;
}
return used;
}
void zkw(){
while( spfa() ){
mark[T] = 1;
while( mark[T] ){
memset(mark,0,sizeof(mark));
dfs(S,INF);
}
}
}
int main(){
scanf("%d%d", &n, &m);
S = 0; T = n*m+m+1;
for( int i = 1; i <= m; i++ )
for( int j = 1; j <= n; j++ )
scanf("%d", &t[i][j]);
for( int i = 1; i <= n*m; i++ ) insert( S, i, 1, 0 );
for( int i = n*m+1; i <= n*m+m; i++ ) insert( i, T, 1, 0 );
for( int i = 1; i <= n; i++ )
for( int j = 1; j <= m; j++ )
for( int k = 1; k <= m; k++ )
insert( (i-1)*m+j, n*m+k, 1, t[k][i]*j );
zkw();
printf("%.2lf", (double)ans/m);
return 0;
}
