//可以网络流，但是要怎么分配每辆车让谁维修以及维修顺序呢。可以考虑每辆车维修时间对总结果的贡献，把每个修车人拆成n个点共n*m个点，//n辆车连向这n*m个点，流量1，费用k*修车时间，其中k(1=<=n)表示这辆车是这个技术人员修的倒数第k俩车，他后面k-1辆被同一个人维修的车//都要等待他修好，因此他的贡献值就是k*维修时间。然后源点连向n辆车，n*m个点连向汇点。#include #include #include #include using namespace std;const int INF=0x7fffffff;const int MAXN=1000;const int MAXM=1000000;int N,a[70][12],tot,head[MAXN+10],pre[MAXN],dis[MAXN];bool vis[MAXN+10];struct Edge{ int to,next,cap,flow,cost;}edge[MAXM+10];void init(int x){ N=x; tot=0; memset(head,-1,sizeof(head));}void add(int x,int y,int w,int c){ edge[tot].to=y; edge[tot].cap=w; edge[tot].cost=c; edge[tot].flow=0; edge[tot].next=head[x]; head[x]=tot++; edge[tot].to=x; edge[tot].cap=0; edge[tot].cost=-c; edge[tot].flow=0; edge[tot].next=head[y]; head[y]=tot++;}bool Spfa(int s,int t){ queue q; for(int i=0;i<=N;i++){ vis[i]=0; dis[i]=INF; pre[i]=-1; } vis[s]=1; dis[s]=0; q.push(s); while(!q.empty()){ int u=q.front();q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(edge[i].cap>edge[i].flow&&dis[v]>dis[u]+edge[i].cost){ dis[v]=dis[u]+edge[i].cost; pre[v]=i; if(!vis[v]){ vis[v]=1; q.push(v); } } } } if(pre[t]==-1) return 0; return 1;}int MaxCostFlow(int s,int t){ int Flow=0,Cost=0; while(Spfa(s,t)){ int Min=INF; for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]) Min=min(Min,edge[i].cap-edge[i].flow); for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){ edge[i].flow+=Min; edge[i^1].flow-=Min; Cost+=edge[i].cost*Min; } Flow+=Min; } return Cost;}int main(){ int n,m; while(scanf("%d%d",&m,&n)==2){ init(n+n*m+1); for(int i=1;i<=n;i++){ add(0,i,1,0); for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=1;k<=n;k++){ add(i,j*n+k,1,k*a[i][j]); } } } for(int i=n+1;i<=n+n*m;i++) add(i,n+n*m+1,1,0); printf("%.2lf\n",1.0*MaxCostFlow(0,n+n*m+1)/(1.0*n)); } return 0;}