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

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

每辆车只需要修一次,所以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 ;
}

最新文章

  1. windows 环境和linux环境下 ping命令的区别:
  2. android 数据下载 工具类
  3. html特殊字符 编码css3 content:&quot;我是特殊符号&quot;
  4. 操作系统win2003 x64的,安装OFFICE2003后,DCOM服务找不到 WORD应用程序服务
  5. AJax 学习笔记二(onreadystatechange的作用)
  6. gcov源码,供学习使用。
  7. Vagrant 快速入门
  8. hdu2025java字符题
  9. C# 判断两个日期是否是同一天
  10. LintCode-字符串查找
  11. protubuf在cocos2dx的应用安装
  12. php 批量导入数据的一种思维
  13. 每天一个linux命令(49)--diff命令
  14. c# 如何读取web.config中的内容(ConfigurationManager)
  15. js变量污染引起的诡异bug
  16. 后台启动mysql
  17. 【转】服务化框架技术选型与京东JSF解密
  18. 九大常用排序算法 python
  19. 基于SOUI开发一个简单的小工具
  20. 8.2.优化SQL语句

热门文章

  1. 长沙Uber优步司机奖励政策(12月28日到1月3日)
  2. js三种存储方式区别
  3. springboot之RMI的使用
  4. Awesome Flask
  5. 一个小白的测试环境docker化之路
  6. python import vs from import
  7. 使用union
  8. C 关键字 标示符 注释
  9. Unity编辑器 - 编辑器控制特效播放
  10. 在Unity中使用LitJson解析json文件