BZOJ 1070 修车(费用流)

如果能想到费用流,这道题就是显然了。

要求所有人的等待平均时间最小,也就是所有人的总等待时间最小。

每辆车只需要修一次,所以s连每辆车容量为1,费用为0的边。 现在需要把每个人拆成n个点,把车和每个人的第k个点连一条容量为1,费用为cost[i][j]*k的边。

最后把每个人拆完后的点向汇点连一条容量为1,费用为0的边。

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
#define T 601
using namespace std;
int n,m,cnt=,ans,t[][];
int d[],q[],from[],head[];
bool mark[];
struct edge{int from,to,next,c,v;}e[];
void ins(int u,int v,int w,int c)
{
cnt++;
e[cnt].from=u;e[cnt].to=v;
e[cnt].next=head[u];head[u]=cnt;
e[cnt].c=c;e[cnt].v=w;
}
void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,,-c);}
bool spfa()
{
memset(mark,,sizeof(mark));
for(int i=;i<=T;i++)d[i]=inf;
int t=,w=;
d[T]=;mark[T]=;q[]=T;
while(t!=w)
{
int now=q[t];t++;if(t==T)t=;
for(int i=head[now];i;i=e[i].next)
if(e[i^].v&&d[e[i].to]>d[now]-e[i].c)
{
d[e[i].to]=d[now]-e[i].c;
if(!mark[e[i].to])
{mark[e[i].to]=;q[w++]=e[i].to;if(w==T)w=;}
}
mark[now]=;
}
if(d[]==inf)return ;
return ;
}
int dfs(int x,int f)
{
if(x==T){mark[T]=;return f;}
int used=,w;
mark[x]=;
for(int i=head[x];i;i=e[i].next)
if(!mark[e[i].to]&&e[i].v&&d[x]-e[i].c==d[e[i].to])
{
w=f-used;
w=dfs(e[i].to,min(e[i].v,w));
ans+=w*e[i].c;
e[i].v-=w;e[i^].v+=w;
used+=w;if(used==f)return f;
}
return used;
}
void zkw()
{
while(spfa())
{
mark[T]=;
while(mark[T])
{
memset(mark,,sizeof(mark));
dfs(,inf);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
scanf("%d",&t[i][j]);
for(int i=;i<=n*m;i++)
insert(,i,,);
for(int i=n*m+;i<=n*m+m;i++)
insert(i,T,,);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=;k<=m;k++)
insert((i-)*m+j,n*m+k,,t[k][i]*j);
zkw();
printf("%.2lf",(double)ans/m);
return ;
}
上一篇:L386 DACBD


下一篇:FSB: 金融科技对金融市场和金融稳定的影响