同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同 的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最 小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人 员维修第i辆车需要用的时间T。
最小平均等待时间，答案精确到小数点后2位。
2 2
3 2
1 4
1.50
数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)
这道题还是挺经典的。 我们考虑到每个技术人员那里修车的人等待的总时间，发现那其实就是\[ 最后一个人修车时间 \times 1 + 倒数第二人修车时间 \times 2 + … + 第一人修车时间 \times x \\ （x表示到这个技术人员处修车的总人数） \] 于是，我们把每个技术人员拆成n个点，代表某个技术人员修的第几辆车，共mn个点 每个顾客向这mn个点连边，边权为\(t \quad 2t \quad 3t \quad …\)，容量为1 S向每个顾客连容量1费用0的边，那mn个点向T连容量1费用0的边。 跑一遍费用流即可。
注意：输入时先输m再输n！！！
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #define INF 2100000000 using namespace std; const int N = 81+65+81*65; struct node{ int v,f,c; node *next,*rev; }pool[N*150],*h[N],*pree[N]; int cnt; void addedge(int u,int v,int f,int c){ node *p=&pool[++cnt],*q=&pool[++cnt]; p->v=v;p->next=h[u];h[u]=p; p->f=f;p->c=c;p->rev=q; q->v=u;q->next=h[v];h[v]=q; q->f=0;q->c=-c;q->rev=p; } int S,T; queue<int> que; int vis[N],d[N],pre[N]; bool spfa(){ int u,v; while(!que.empty()) que.pop(); for(int i=S;i<=T;i++) d[i]=INF; d[S]=0; vis[S]=1; que.push(S); while(!que.empty()){ u=que.front(); que.pop(); vis[u]=0; for(node *p=h[u];p;p=p->next) if(p->f && d[v=p->v]>d[u]+p->c){ d[v]=d[u]+p->c; pre[v]=u; pree[v]=p; if(!vis[v]) { vis[v]=1; que.push(v); } } } return d[T]!=INF; } int MCMF(){ int f=0,c=0,u,w; while(spfa()){ u=T; w=INF; while(u!=S){ w=min(w,pree[u]->f); u=pre[u]; } f+=w; c+=w*d[T]; u=T; while(u!=S){ pree[u]->f-=w; pree[u]->rev->f+=w; u=pre[u]; } } return c; } int n,m; int main() { int x; scanf("%d%d",&m,&n); /**/ S=0; T=m*n+n+1; for(int i=1;i<=n;i++){ addedge(S,i,1,0); for(int j=1;j<=m;j++){ scanf("%d",&x); for(int k=0;k<n;k++) addedge(i,n+k*m+j,1,x*(k+1)); } } for(int i=1;i<=m;i++) for(int k=0;k<n;k++) addedge(n+k*m+i,T,1,0); double ans=MCMF(); printf("%.2lf\n",ans/(double)n); return 0; }转载于:https://www.cnblogs.com/lindalee/p/8638289.html
