百度网站提交收录入口,温州做微网站设计,青岛网站建设最便宜,云南网站建设一条龙1070: [SCOI2007]修车 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 5860 Solved: 2487[Submit][Status][Discuss]Description 同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员#xff0c;不同的技术人员对不同 的车进行维修所用的时间是不… 1070: [SCOI2007]修车 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 5860 Solved: 2487[Submit][Status][Discuss] Description 同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员不同的技术人员对不同 的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序使得顾客平均等待的时间最 小。 说明顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 Input 第一行有两个m,n表示技术人员数与顾客数。 接下来n行每行m个整数。第i1行第j个数表示第j位技术人 员维修第i辆车需要用的时间T。 Output 最小平均等待时间答案精确到小数点后2位。 Sample Input 2 2 3 2 1 4 Sample Output 1.50 把修车师傅拆成 n*m个修车师傅 然后具体 // 还是看这里吧http://hzwer.com/2877.html 1 #includecstdio2 #includequeue3 #includecstring4 #includealgorithm5 using namespace std;6 const int N1000;7 const int M5e588;8 const int INF0x3f3f3f3f;9 int mp[88][11];
10 struct node{
11 int u,v,flow,cost,next;
12 }e[M];
13 int tot,head[N],pre[N],C[N],F[N],V[N],n,m;
14 void add(int u,int v,int flow,int cost){
15 e[tot].uu;e[tot].vv;e[tot].flowflow;e[tot].costcost;e[tot].nexthead[u];head[u]tot;
16 e[tot].uv;e[tot].vu;e[tot].flow0;e[tot].cost-cost;e[tot].nexthead[v];head[v]tot;
17 }
18 int SPFA(int s,int t){
19 memset(pre,-1,sizeof(pre));
20 for(int i1;it1;i) F[i]0,C[i]INF,V[i]0;
21 queueintQ;
22 Q.push(s);
23 C[0]0,F[0]INF,V[0]1;
24 while(!Q.empty()){
25 int uQ.front();
26 Q.pop();
27 V[u]0;
28 for(int ihead[u];i1;ie[i].next){
29 int ve[i].v,fe[i].flow,ce[i].cost;
30 if(f0C[v]C[u]c) {
31 C[v]C[u]c;
32 pre[v]i;
33 F[v]min(f,F[u]);
34 if(!V[v]) V[v]1,Q.push(v);
35 }
36 }
37 }
38 return F[t];
39 }
40 int MCMF(int s,int t){
41 int ans0,temp;
42 while(tempSPFA(s,t)){
43 for(int ipre[t];i1;ipre[e[i].u]) {
44 anstemp*e[i].cost;
45 e[i].flow-temp;
46 e[i^1].flowtemp;
47 }
48 }
49 return ans;
50 }
51 int main(){
52 memset(head,-1,sizeof(head));
53 scanf(%d%d,m,n);
54 for(int i1;in;i)
55 for(int j1;jm;j)
56 scanf(%d,mp[i][j]);//mp[i][j]顾客--修车人员
57 int st0,edm*nn1;
58 for(int i1;in*m;i) add(0,i,1,0);
59 for(int in*m1;in*mn;i) add(i,ed,1,0);
60 for(int i1;im;i)
61 for(int j1;jn;j)
62 for(int k1;kn;k)
63 add((i-1)*nj,n*mk,1,mp[k][i]*j);
64 int ctMCMF(st,ed);
65 printf(%.2f\n,double(ct)/n);
66 } 转载于:https://www.cnblogs.com/mfys/p/7182910.html
