本文共 2614 字，大约阅读时间需要 8 分钟。

$得先把题意转化一下,否则无法建图$

$为啥没办法建图?因为每个师傅修每辆车的代价不是$定值

$不是定值,就想办法变成定值。$

$考虑某个师傅一次修车a_1,a_2,a_3,a_4$

$那么a_1的等待时间是a_1$

$a_2的等待时间是a_1+a_2$

$a_3的等待时间是a_1+a_2+a_3$

$a_4的等待时间是a_1+a_2+a_3+a_4$

$设某个师傅修了x辆车$

$最后修的车的代价只需要在原来基础上乘1$

$倒数第二次修车的代价只需要在原来的基础上乘2$

$......................$

$于是把m个师傅分成n层$

$第i层表示修倒数第i辆车的师傅,那么代价乘以i$

$每层的每个师傅向每一辆车连边即可$

$跑最小费用最大流,对于每个师傅而言一定是依次选择$

$修倒数第1辆车,修倒数第2辆车,实际上这也是连续的$

#include 
   
    using namespace std;const int maxn=2e5+10;const int inf=1e9; int n,m,s,t,c[509][509];struct edge{	int to,nxt,flow,w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int w,int flow){	d[++cnt]=(edge){v,head[u],flow,w},head[u]=cnt;	d[++cnt]=(edge){u,head[v],0,-w},head[v]=cnt;}int dis[maxn],mincost,vis[maxn],pre[maxn],flow[maxn];bool spfa(){	for(int i=0;i<=t;i++)	dis[i]=inf,vis[i]=0;	dis[s]=0,flow[s]=inf;	queue
    
     q; q.push( s );	while( !q.empty() )	{		int u=q.front(); q.pop();		vis[u]=0;		for(int i=head[u];i;i=d[i].nxt )		{			int v=d[i].to;			if( d[i].flow&&dis[v]>dis[u]+d[i].w )			{				dis[v]=dis[u]+d[i].w;				flow[v]=min(flow[u],d[i].flow);				pre[v]=i;				if(	!vis[v] )	vis[v]=1,q.push( v );			}		}	}	return dis[t]!=inf;}int dinic(){	while( spfa() )	{		int x=t;		mincost+=flow[t]*dis[t];		while( x!=s )		{			int i=pre[x];			d[i].flow-=flow[t];			d[i^1].flow+=flow[t];			x=d[i^1].to;		}	}}int main(){	cin >> m >> n;//m位技术人员,n位车主	for(int i=1;i<=n;i++)	for(int j=1;j<=m;j++)		cin >> c[i][j];	s=0,t=n*m+n+1;	for(int i=1;i<=n*m;i++)	add(s,i,0,1);//源点连向每个师傅	for(int i=1;i<=m;i++)//枚举每个师傅 	for(int j=1;j<=n;j++)//枚举每个车 	for(int k=1;k<=n;k++)//枚举每个时刻 	{		int id=(k-1)*m+i;//第k层图,每层图有m个师傅		add(id,j+n*m,c[j][i]*k,1);		} 	for(int i=1;i<=n;i++)	add(n*m+i,t,0,1);	dinic();	printf("%.2lf",double(mincost)/(n*1.0) );}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108165978 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！