同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间 Ti,j 。 (2<=M<=9, 1<=N<=60, 1<=T<=1000)
巧妙建图的费用流。 这题看似数据较小，但是搜索还是很慢。对于资源分配的问题可以往网络流方面考虑。 如何建图呢，一般最直接的想法是对于每个技术人员按时刻拆点，但是发现这样搞点数和边数太大了，复杂度基本上承受不了。 这时候就需要特殊的建图技巧了，考虑一个分配方案，某辆车i在某个技术人员j上修理，对答案的贡献为:
Ti,j∗(同样给技术人员j，且在车i之后修理的车辆数+1) 很好理解，不给技术人员j修理的车没有受到任何影响，而排队排在他之后的车都会增加 Tij 的等待时间（还要把自己算上，所以+1）。分析到这里我们发现，只要知道每辆车排在这个队伍的第几个就能知道总贡献了。 于是我们把每个技术人员i拆成n个点，其中第j个点表示在i这队排的倒数第j个位置，记为 ai,j 。 增加超级源S与超级源汇T。 对于每辆车i, 连边 S->i，容量1，费用0 对于每辆车i, 向n*m个拆出的技术人员连边 i-> aj,k ，容量1，费用 Ti,j∗k 对于n*m个拆出的技术人员，连边 ai,j -> T，容量1，费用0
显然上述建图是对的。然后跑费用流即可，求出费用是总等待时间，除以n即是答案。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=1005,maxe=100005; int nxt[maxe],S,T,fir[maxn],tot=1; int f[maxn],dis[maxn],path[maxn],ans1,ans2; struct Edge { int from,to,cap,flow,cost; Edge(int x1=0,int x2=0,int x3=0,int x4=0,int x5=0):from(x1),to(x2),cap(x3),flow(x4),cost(x5){} } Es[maxe]; queue <int> que; bool vis[maxn]; void add(int x,int y,int w,int c){ Es[++tot]=Edge(x,y,w,0,c); nxt[tot]=fir[x]; fir[x]=tot; Es[++tot]=Edge(y,x,0,0,-c); nxt[tot]=fir[y]; fir[y]=tot; } bool Find_Spfa(int s,int t,int &MaxFlow,int &MinCost){ memset(f,0,sizeof(f)); f[s]=1e+9; memset(dis,63,sizeof(dis)); dis[s]=0; memset(vis,0,sizeof(vis)); while(!que.empty()) que.pop(); que.push(s); while(!que.empty()){ int x=que.front(); que.pop(); vis[x]=false; for(int j=fir[x];j;j=nxt[j]){ if(Es[j].cap>Es[j].flow&&dis[x]+Es[j].cost<dis[Es[j].to]){ dis[Es[j].to]=dis[x]+Es[j].cost; path[Es[j].to]=j; f[Es[j].to]=min(f[x],Es[j].cap-Es[j].flow); if(!vis[Es[j].to]) vis[Es[j].to]=true, que.push(Es[j].to); } } } if(!f[t]) return false; MaxFlow+=f[t]; MinCost+=f[t]*dis[t]; for(int i=t;i!=s;i=Es[path[i]].from){ Es[path[i]].flow+=f[t]; Es[path[i]^1].flow-=f[t]; } return true; } int n,m,a[maxn][maxn]; int main(){ freopen("bzoj1070.in","r",stdin); freopen("bzoj1070.out","w",stdout); scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); S=n*(m+1)+1; T=n*(m+1)+2; for(int i=1;i<=n;i++) add(S,n*m+i,1,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=n;k++) add(n*m+i,(j-1)*n+k,1,a[i][j]*k); for(int i=1;i<=m;i++) for(int k=1;k<=n;k++) add((i-1)*n+k,T,1,0); ans1=ans2=0; while(Find_Spfa(S,T,ans1,ans2)); printf("%.2lf\n",((double)ans2)/n); return 0; }