题目描述

同一时刻有 NN 位车主带着他们的爱车来到了汽车维修中心。

维修中心共有 MM 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。

现在需要安排这 MM 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。

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

输入格式

第一行有两个数 M,NM,N，表示技术人员数与顾客数。

接下来 nn 行，每行 MM 个整数。第 i+1i+1 行第 jj 个数表示第 jj 位技术人员维修第 ii 辆车需要用的时间 T_{i,j}Ti,j​。

输出格式

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

输入输出样例

输入 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
2 2
3 2
1 4
输出 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
1.50

说明/提示

对于 100\%100% 的数据，2\le M\le 92≤M≤9，1\le N\le 601≤N≤60，1\le T\le 10^31≤T≤103。

 

思路

　　对于每个修车工人，由于不限量接单，那么他修第 i 台车时，耗费的时间就是 Ti, j ，那么第一个车主的等待时间就是 T1，第二个就是 T1 + T2，可推第 n 个车主的等待时间就是 T1 + T2 + ... + Tn。

　　那么所有车主加起来时间消耗就是 N*T1 + (N - 1)*T2 + ... + Tn。

　　所以把工人拆成 N 个点，对于每台车向工人按上述花费连一条流量为 1 的边，跑最小花费最大流，最后将最小费用 / N，就能得到所有人等待时间的平均值。

 

CODE

 

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 
  4 using namespace std;
  5 typedef long long LL;
  6                    
  7 template<class T>inline void read(T &res)
  8 {
  9     char c;T flag=1;
 10     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 11     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 12 }
 13 
 14 const int MAXN = 2e3 + 5;
 15 const int inf = 0x3f3f3f3f;
 16 
 17 int N, M;
 18 
 19 struct Edge{
 20     int to, val, cost;
 21     Edge *next, *ops;
 22     Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
 23 };
 24 
 25 Edge *head[MAXN << 1];
 26 
 27 void BuildGraph(int u, int v, int w, int c) {
 28     head[u] = new Edge(v, w, c, head[u]);
 29     head[v] = new Edge(u, 0, -c, head[v]);
 30     head[u]->ops = head[v]; head[v]->ops = head[u];
 31 }
 32 
 33 namespace zkw{
 34     int s, t, ans, res;
 35     int dis[MAXN << 1];
 36     bool vis[MAXN << 1];
 37     bool Spfa() {
 38         memset(vis, false, sizeof vis);
 39         memset(dis, 0x3f, sizeof dis);
 40         deque<int> q;
 41         q.push_back(s);
 42         vis[s] = true; dis[s] = 0;
 43         while (!q.empty()) {
 44             int u = q.front(); q.pop_front(); vis[u] = false;
 45             for (Edge *e = head[u]; e; e = e->next) {
 46                 int v = e->to;
 47                 if (e->val > 0 && dis[u] + e->cost < dis[v]) {
 48                     dis[v] = dis[u] + e->cost;
 49                     if (!vis[v]) {
 50                         vis[v] = true;
 51                         if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
 52                         else q.push_back(v);
 53                     }
 54                 }
 55             }
 56         }
 57         return dis[t] < inf;
 58     }
 59 
 60     int Dfs(int u, int flow) {
 61         if (u == t) {
 62             vis[u] = true;
 63             res += flow;
 64             return flow;
 65         }
 66         int used = 0; vis[u] = true;
 67         for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
 68             int v = e->to;
 69             if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
 70                 int mi = Dfs(v, min(e->val, flow - used));
 71                 if (mi) {
 72                     e->val -= mi;
 73                     e->ops->val += mi;
 74                     ans += e->cost * mi;
 75                     used += mi;
 76                 }
 77                 if (used == flow) break;
 78             }
 79         }
 80         return used;
 81     }
 82 
 83     void Work() {
 84         res = 0; ans = 0;
 85         while (Spfa()) {
 86             vis[t] = true;
 87             while (vis[t]) {
 88                 memset(vis, false, sizeof vis);
 89                 Dfs(s, inf);
 90             }
 91         }
 92     }
 93 }
 94 
 95 signed main() {
 96     read(M);
 97     read(N);
 98     int temp = 0;
 99     temp = M * N;
100     zkw :: s = 0; zkw :: t = temp + N + 1;
101     int s = 0, t = temp + N + 1;
102     for ( int i = 1; i <= N; ++i ) {
103         for ( int j = 1; j <= M; ++j ) {
104             int x;
105             read(x);
106             for ( int k = 1; k <= N; ++k ) {
107                 BuildGraph(i, N + (j - 1) * N + k, 1, x * k);
108             }
109         }
110     }
111     for ( int i = 1; i <= N; ++i ) {
112         BuildGraph(s, i, 1, 0);
113     }
114     for ( int i = 1; i <= M; ++i ) {
115         for ( int j = 1; j <= N; ++j ) {
116             BuildGraph(N + (i - 1) * N + j, t, 1, 0);
117         }
118     }
119     zkw :: Work();
120     //dbg(zkw ::ans);
121     printf("%.2lf\n", (double)zkw ::ans / (double)N);
122     return 0;
123 }
zkw费用流

 

#include  < bits/stdc++.h >
#define  dbg( x ) cout  <<  #x  <<  " = "  << x  << endl

using  namespace std ;
typedef  long  long LL ;
                   
template < class T > inline  void  read(T  & res )
{
     char c ;T flag = 1 ;
     while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
     while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}

const  int MAXN  =  2 e 3  +  5 ;
const  int inf  =  0x 3f3f3f3f ;

int N , M ;

struct Edge {
     int to , val , cost ;
    Edge  *next ,  *ops ;
     Edge( int  to ,  int  val ,  int  cost , Edge  * next ):  to(to ),  val(val ),  cost(cost ),  next(next ){}
};

Edge  * head [MAXN  <<  1 ];

void  BuildGraph( int  u ,  int  v ,  int  w ,  int  c )  {
     head [u ]  =  new  Edge(v , w , c ,  head [u ]);
     head [v ]  =  new  Edge(u ,  0 ,  -c ,  head [v ]);
     head [u ]-> ops  =  head [v ];  head [v ]-> ops  =  head [u ];
}

namespace zkw {
     int s , t , ans , res ;
     int  dis [MAXN  <<  1 ];
     bool  vis [MAXN  <<  1 ];
     bool  Spfa()  {
         memset(vis ,  false , sizeof vis );
         memset(dis ,  0x 3f , sizeof dis );
        deque <int> q ;
         q .push_back(s );
         vis [s ]  =  true ;  dis [s ]  =  0 ;
         while  ( ! q .empty())  {
             int u  =  q .front();  q .pop_front();  vis [u ]  =  false ;
             for  (Edge  *e  =  head [u ]; e ; e  =  e -> next )  {
                 int v  =  e -> to ;
                 if  ( e -> val  >  0  &&  dis [u ]  +  e -> cost  <  dis [v ])  {
                     dis [v ]  =  dis [u ]  +  e -> cost ;
                     if  ( ! vis [v ])  {
                         vis [v ]  =  true ;
                         if  ( ! q .empty()  &&  dis [v ]  <  dis [ q .front()])  q .push_front(v );
                         else  q .push_back(v );
                     }
                 }
             }
         }
         return  dis [t ]  < inf ;
     }

     int  Dfs( int  u ,  int  flow )  {
         if  (u  == t )  {
             vis [u ]  =  true ;
            res  += flow ;
             return flow ;
         }
         int used  =  0 ;  vis [u ]  =  true ;
         for  (Edge  *e  =  head [u ]; e ; e  =  e -> next )  { //当前弧就不加了
             int v  =  e -> to ;
             if  (( ! vis [v ]  || v  == t )  &&  e -> val  &&  dis [u ]  +  e -> cost  ==  dis [v ])  {
                 int mi  =  Dfs(v ,  min( e -> val , flow  - used ));
                 if  (mi )  {
                     e -> val  -= mi ;
                     e -> ops -> val  += mi ;
                    ans  +=  e -> cost  * mi ;
                    used  += mi ;
                 }
                 if  (used  == flow )  break;
             }
         }
         return used ;
     }

     void  Work()  {
        res  =  0 ; ans  =  0 ;
         while  (Spfa())  {
             vis [t ]  =  true ;
             while  ( vis [t ])  {
                 memset(vis ,  false , sizeof vis );
                 Dfs(s , inf );
             }
         }
     }
}

signed  main()  {
     read(M );
     read(N );
     int temp  =  0 ;
    temp  = M  * N ;
    zkw  :: s  =  0 ; zkw  :: t  = temp  + N  +  1 ;
     int s  =  0 , t  = temp  + N  +  1 ;
     for  (  int i  =  1 ; i  <= N ;  ++i  )  {
         for  (  int j  =  1 ; j  <= M ;  ++j  )  {
             int x ;
             read(x );
             for  (  int k  =  1 ; k  <= N ;  ++k  )  {
                 BuildGraph(i , N  +  (j  -  1 )  * N  + k ,  1 , x  * k );
             }
         }
     }
     for  (  int i  =  1 ; i  <= N ;  ++i  )  {
         BuildGraph(s , i ,  1 ,  0 );
     }
     for  (  int i  =  1 ; i  <= M ;  ++i  )  {
         for  (  int j  =  1 ; j  <= N ;  ++j  )  {
             BuildGraph(N  +  (i  -  1 )  * N  + j , t ,  1 ,  0 );
         }
     }
    zkw  ::  Work();
    //dbg(zkw ::ans);
     printf( " %.2lf \n " ,  ( double )zkw  ::ans  /  ( double )N );
     return  0 ;
}