題目描述

同一時刻有N位車主帶著他們的愛車來到了汽車維修中心。維修中心共有M位技術(shù)人員，不同的技術(shù)人員對不同的車進(jìn)行維修所用的時間是不同的。現(xiàn)在需要安排這M位技術(shù)人員所維修的車及順序，使得顧客平均等待的時間最小。

說明：顧客的等待時間是指從他把車送至維修中心到維修完畢所用的時間。

輸入輸出格式

輸入格式：

?

第一行有兩個數(shù)M,N，表示技術(shù)人員數(shù)與顧客數(shù)。

接下來n行，每行m個整數(shù)。第i+1行第j個數(shù)表示第j位技術(shù)人員維修第i輛車需要用的時間T。

?

輸出格式：

?

最小平均等待時間，答案精確到小數(shù)點(diǎn)后2位。

?

輸入輸出樣例

輸入樣例#1：

2 2
3 2
1 4

輸出樣例#1：

1.50

說明

(2<=M<=9,1<=N<=60), (1<=T<=1000)

思路：構(gòu)圖+費(fèi)用流

直接看了題解，這種構(gòu)圖，我只能說：“牛逼！”

把n個工人拆成n*m個，這樣每個點(diǎn)就表示某個時段（并非順次對應(yīng)）的工人了，然后與n個顧客連邊，邊權(quán)為維修用時*工人工作時段。

然后跑一個費(fèi)用流，就是總用時f（其實是每個顧客等待用時之和），然后ans=f/n。

代碼實現(xiàn)：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int inf=2139062143;
 4 const int maxn=1000;
 5 const int maxm=80000;
 6 int m,n,s,t,nf,nc,tc;
 7 int a,b,c;
 8 inline int min_(int x,int y){return x<y?x:y;}
 9 int h[maxn],hs=1;
10 struct edge{int s,n,w,f;}e[maxm];
11 void add(int q,int z,int f){
12     e[++hs]=(edge){z,h[q],1,f},h[q]=hs;
13     e[++hs]=(edge){q,h[z],0,-f},h[z]=hs;
14 }
15 int w[maxn],p[maxn][2],q[maxm],head,tail;
16 long long la,lb;
17 int spfa(){
18     memset(w,0x7f,sizeof(w));
19     head=tail=0;
20     q[head++]=s,w[s]=0;
21     while(head>tail){
22         a=q[tail++];
23         for(int i=h[a];i;i=e[i].n)
24         if(e[i].w){
25             la=e[i].f,lb=w[a],la+=lb,lb=w[e[i].s];
26             if(la<lb){
27                 w[e[i].s]=la;
28                 p[e[i].s][0]=i;
29                 p[e[i].s][1]=a;
30                 q[head++]=e[i].s;
31             }
32         }
33     }
34     return w[t];
35 }
36 int ap(int k,int v){
37     if(k==s) return v;
38     int ret=ap(p[k][1],min_(e[p[k][0]].w,v));
39     e[p[k][0]].w-=ret;
40     e[p[k][0]^1].w+=ret;
41     return ret;
42 }
43 bool Dinic(){
44     nc=spfa();
45     if(nc==inf) return false;
46     nf=ap(t,inf);
47     tc+=nf*nc;
48     return true;
49 }
50 int main(){
51     freopen("scoi2007_repair.in","r",stdin);
52     freopen("scoi2007_repair.out","w",stdout);
53     scanf("%d%d",&m,&n);
54     s=0,t=n*m+n+1;
55     for(int i=1;i<=n;i++) add(s,i,0);
56     for(int i=n+1;i<=n*m+n;i++) add(i,t,0);
57     for(int i=1;i<=n;i++)
58     for(int j=1;j<=m;j++){
59         scanf("%d",&a);
60         for(int k=1;k<=n;k++) add(i,n*j+k,a*k);
61     }
62     while(Dinic());
63     printf("%.2lf\n",1.0*tc/n);
64     return 0;
65 }

aaa~反邊費(fèi)用忘記調(diào)成負(fù)數(shù)了。

另外，仍然建議去COGS，因為有數(shù)據(jù)。

題目來源：洛谷,COGS

轉(zhuǎn)載于:https://www.cnblogs.com/J-william/p/6600198.html

總結(jié)

以上是生活随笔為你收集整理的[SCOI2007]修车的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。