即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[bzoj1070][SCOI2007]修车 费用流

编程语言 youhavepeople 17℃ 0评论
本文目录
[隐藏]

1.1070: [SCOI2007]修车

Time Limit: 1 Sec  Memory Limit:
128 MB


[Submit][Status][Discuss]

2.Description

  同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员,不同的技术人员对不同


的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序,使得顾客平均等待的时间最


小。 说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

3.Input

  第一行有两个m,n,表示技术人员数与顾客数。 接下来n行,每行m个整数。第i+1行第j个数表示第j位技术人


员维修第i辆车需要用的时间T。

4.Output

  最小平均等待时间,答案精确到小数点后2位。

5.Sample Input

2 2


3 2


1 4

6.Sample Output

1.50

7.HINT

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

8.Source

太晚了,不想写题解了
#include
#include
#include
#include
#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;
}


转载请注明:CodingBlog » [bzoj1070][SCOI2007]修车 费用流

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情