P2053 [SCOI2007]修车(逆向思维分层建图)

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

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

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

考 虑 某 个 师 傅 一 次 修 车 a 1 , a 2 , a 3 , a 4 考虑某个师傅一次修车a_1,a_2,a_3,a_4 考虑某个师傅一次修车a1​,a2​,a3​,a4​

那 么 a 1 的 等 待 时 间 是 a 1 那么a_1的等待时间是a_1 那么a1​的等待时间是a1​

a 2 的 等 待 时 间 是 a 1 + a 2 a_2的等待时间是a_1+a_2 a2​的等待时间是a1​+a2​

a 3 的 等 待 时 间 是 a 1 + a 2 + a 3 a_3的等待时间是a_1+a_2+a_3 a3​的等待时间是a1​+a2​+a3​

a 4 的 等 待 时 间 是 a 1 + a 2 + a 3 + a 4 a_4的等待时间是a_1+a_2+a_3+a_4 a4​的等待时间是a1​+a2​+a3​+a4​

$设某个师傅修了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;queueq; 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) );
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！