最小费用最大流。
将每个技术人员拆成车数个点，技术人员i的第j个点代表技术人员i修的倒数第j辆车。
源点向所有技术人员点连一条容量为1费用为0的边。
所有技术人员点向所有车点连边：技术人员i的第j个点向第k个车点连一条容量为1费用为T[k][i]*j的边。
所有车点向汇点连一条容量为1费用为0的边。
由于每辆车只能被修一次，如果将车拆点则无法保证这一性质，所以考虑将人拆点。因为不知道每个人会修几辆车，于是将点定义为该工人修的倒数第i辆车，这样便能将每个点对之后的影响加在这个点值里。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int dian=605; 8 const int bian=100005; 9 int h[dian],nxt[bian],ver[bian],val[bian],cos[bian],minn[dian],with[dian];10 int d[dian],v[dian];11 int map[65][15];12 int n,m,tot;13 int S,T;14 void add(int a,int b,int c,int d){15 tot++;ver[tot]=b;val[tot]=c;cos[tot]=d;nxt[tot]=h[a];h[a]=tot;16 tot++;ver[tot]=a;val[tot]=0;cos[tot]=-d;nxt[tot]=h[b];h[b]=tot;17 }18 bool tell(){19 memset(v,0,sizeof(v));20 memset(d,0x3f,sizeof(d));21 memset(with,0,sizeof(with));22 memset(minn,0x3f,sizeof(minn));23 queue q;24 q.push(S);25 v[S]=1;26 d[S]=0;27 while(!q.empty()){28 int x=q.front();29 q.pop();30 v[x]=0;31 for(int i=h[x];i;i=nxt[i]){32 int y=ver[i];33 if(d[y]>d[x]+cos[i]&&val[i]){34 d[y]=d[x]+cos[i];35 minn[y]=min(minn[x],val[i]);36 with[y]=i;37 if(!v[y]){38 v[y]=1;39 q.push(y);40 }41 }42 }43 }44 if(d[T]==0x3f3f3f3f)45 return 0;46 return 1;47 }48 int zeng(){49 for(int i=T;i!=S;i=ver[with[i]^1]){50 val[with[i]]-=minn[T];51 val[with[i]^1]+=minn[T];52 }53 return d[T]*minn[T];54 }55 int dinic_cost(){56 int r=0;57 while(tell())58 r+=zeng();59 return r;60 }61 int main(){62 memset(h,0,sizeof(h));63 memset(nxt,0,sizeof(nxt));64 tot=1;65 scanf("%d%d",&m,&n);66 S=n*m+n+1,T=n*m+n+2;67 for(int i=1;i<=n;i++)68 for(int j=1;j<=m;j++)69 scanf("%d",&map[i][j]);70 for(int i=1;i<=m;i++)71 for(int j=1;j<=n;j++){72 add(S,(i-1)*n+j,1,0);73 for(int k=1;k<=n;k++)74 add((i-1)*n+j,n*m+k,1,map[k][i]*j);75 }76 for(int i=1;i<=n;i++)77 add(n*m+i,T,1,0);78 printf("%.2f",(double)dinic_cost()/n);79 return 0;80 }
注意n和m的定义和读入。