BZOJ 1070修车 费用流(拆点)

题意:同一时刻有N位车主到维修中心,告诉你a[i][j]第i个师傅修第j个人的车需要的时间. 现在需要安排这M位师傅所维修的车及顺序,使得顾客平均等待的时间最小. 顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间. 2<=M<=9,1<=N<=60 左边定点i为师傅 右边点j为车主 花费为a[i][j] 跑流量为n的最小费用最大流. wawawawaawa,一个师傅修多辆车时 等待时间需要累加!! 比如某师傅修了2,1,4 则2,1,4总共等待时间为3*a[2]+2*a[1]+a[4].怎么表示累加时间? 拆点:把每个师傅拆成n个点,每个点都与源点连流量1,费用0的边.

每个师傅拆出来的第i个点和每辆车相连,费用为i*a[x][y],代表:这是该师傅修的倒数第i俩车.(费用得到累加.)

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; const int N=2e3+20,inf=0x3f3f3f3f; double n; int m,s,t; int cnt,head[N]; struct node{ int u,to,next,flow,cost; }e[N*N]; void add(int u,int v,int flow,int cost) { e[cnt].u=u,e[cnt].to=v,e[cnt].flow=flow,e[cnt].cost=cost; e[cnt].next=head[u]; head[u]=cnt++; } void Add(int u,int v,int flow,int cost) { add(u,v,flow,cost); add(v,u,0,-cost); } int pre[N],inq[N],f[N],c[N]; int SPFA(int s,int t) { memset(pre,-1,sizeof(pre)); queue<int> q; for(int i=0;i<=t;i++) c[i]=inf,inq[i]=0,f[i]=0; q.push(s),c[s]=0,inq[s]=1,f[s]=inf; while(!q.empty()) { int u=q.front(); q.pop(),inq[u]=0; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].to,w=e[i].cost; if(e[i].flow>0&&c[v]>c[u]+w) { c[v]=c[u]+w; f[v]=min(f[u],e[i].flow); pre[v]=i; if(!inq[v]) inq[v]=1,q.push(v); } } } return f[t]; } int a[N][N]; int MCMF(int s,int t) { int ans=0,i,tmp; while(tmp=SPFA(s,t)) { for(int i=pre[t];i!=-1;i=pre[e[i].u]) { int res=tmp*e[i].cost; ans+=tmp*e[i].cost; e[i].flow-=tmp; e[i^1].flow+=tmp; } } return ans; } int main() { int x; cin>>m>>n; s=0,t=m*n+n+1; memset(head,-1,sizeof(head)); cnt=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) Add((k-1)*m+j,m*n+i,1,k*a[i][j]); for(int j=1;j<=n*m;j++) Add(s,j,1,0); for(int i=1;i<=n;i++) Add(m*n+i,t,1,0); double ans=MCMF(s,t); ans=ans/n; printf("%.2lf\n",ans); return 0; }