题目
做法
假设一位修理员修理的顺序分别为\(a[1],a[2]...a[n]\)，时间分别为\(w[1],w[2]...w[3]\)
总等待时间为\(\sum\limits_{i=1}^n w[1]*(n-i+1)\)
则\(S\)(超级源点)向n辆车连(1流量,0费用)的边，右部分是\(n*m\)个二元组\((x,y)\)表示第\(x\)个人修的第\(y\)辆车
左右连边跑最大流最小费用
My complete code
#includeusing namespace std;typedef int LL;const LL maxn=1e6+9, inf=0x3f3f3f3f;struct node{ LL to,nxt,f,c;}dis[maxn];LL n,m,num,S,T,ans;LL head[maxn],pre_v[maxn],pre_d[maxn],flow[maxn],cost[maxn],w[101][101];bool visit[maxn];inline void Add(LL u,LL v,LL f,LL c){ dis[++num]=(node){v,head[u],f,c}, head[u]=num;}inline LL Id(LL i,LL j){ return (i-1)*n+j; }inline bool Spfa(){ queue que; que.push(S); memset(flow,inf,sizeof(flow)), memset(pre_d,0,sizeof(pre_d)), memset(pre_v,0,sizeof(pre_v)); memset(cost,inf,sizeof(cost)); cost[S]=0; while(que.size()){ LL u(que.front()); que.pop(); visit[u]=false; for(LL i=head[u];i!=-1;i=dis[i].nxt){ LL v(dis[i].to); if(dis[i].f && cost[v]>cost[u]+dis[i].c){ cost[v]=cost[u]+dis[i].c; flow[v]=min(flow[u], dis[i].f); pre_v[v]=u, pre_d[v]=i; if(!visit[v]){ visit[v]=true; que.push(v); } } } }return pre_v[T];}inline void Ek(){ while(Spfa()){ ans+=cost[T]*flow[T]; for(LL i=T;i!=S;i=pre_v[i]){ dis[pre_d[i]].f-=flow[T], dis[pre_d[i]^1].f+=flow[T]; } } printf("%.2lf",1.0*ans/n);}int main(){ cin>>m>>n; for(LL i=1;i<=n;++i) for(LL j=1;j<=m;++j) cin>>w[j][i]; S=n*m+n+2, T=n*m+n+1; memset(head,-1,sizeof(head)), num=-1; for(LL i=1;i<=n;++i) Add(S,i,1,0), Add(i,S,0,0); for(LL i=1;i<=m;++i) for(LL j=1;j<=n;++j){ Add(n+Id(i,j),T,1,0), Add(T,n+Id(i,j),0,0); } for(LL i=1;i<=m;++i) for(LL j=1;j<=n;++j){ LL v(n+Id(i,j)); for(LL k=1;k<=n;++k) Add(k,v,1,w[i][k]*j), Add(v,k,0,-w[i][k]*j); } Ek(); return 0;}