原题链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1070

题意:问你如何分配老司机使得每部车的等待时间之和最短。

解题思路:本题不易正做,考虑逆向解答,显然我们有对于一部车,我们枚举它被第i个老司机倒数第j个修,这样的带来的等待时间便是一定的。因此我们考虑枚举建点,建第j个老司机倒数第k个修第i部车,这样的话我们可以比较轻松的就可以建出一个网络,然后跑一遍最小费用最大流即可。

AC代码(用的比较low的SPFA费用流,但是在优化常数后就比学长写的P-D慢了一点)

#include<stdio.h>
#include<string.h>
#define inf 0x7fffffff
#define min(a,b) (a<b?a:b)
#define S 0
#define T 1001
#define length 2005
struct zxy{int to,next,c,v;}edge[];
int n,m,cnt=,head[],dist[],que[],pre[];
bool vis[];
inline int in(){
int x=,f=;char ch=getchar();
while(ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline void ins(int x,int y,int v,int l){
edge[++cnt].to=y,edge[cnt].next=head[x],edge[cnt].v=v,edge[cnt].c=l,head[x]=cnt;
edge[++cnt].to=x,edge[cnt].next=head[y],edge[cnt].v=,edge[cnt].c=l*(-),head[y]=cnt;
}
bool SPFA_costflow(int s,int e){
memset(dist,/,sizeof(dist));
register int h=,t=,w,v;
que[]=s; vis[s]=; dist[s]=;
while(h!=t){
(++h)%=length;
w=que[h];
for (register int i=head[w]; i; i=edge[i].next)
if (dist[edge[i].to]>dist[w]+edge[i].c&&edge[i].v){
v=edge[i].to; pre[v]=i;
dist[v]=dist[w]+edge[i].c;
if (!vis[v]){
vis[v]=;
if (dist[v]<dist[h+]){
que[h]=v;
h=(h-+length)%length;
}
else{
(++t)%=length;
que[t]=v;
}
}
}
vis[w]=;
}
return dist[e]!=dist[T+];
}
int cost_flow(int s,int t){
int cost=;
while(SPFA_costflow(s,t)){
int mi=inf;
for (register int i=t; i; i=edge[pre[i]^].to)
mi=min(mi,edge[pre[i]].v);
for (register int i=t; i; i=edge[pre[i]^].to)
edge[pre[i]].v-=mi,edge[pre[i]^].v+=mi;
cost+=dist[t]*mi;
}
return cost;
}
void init(){
m=in(),n=in();
for (int i=; i<=n; ++i){
for (int j=; j<=m; ++j){
int l=in();
for (int k=; k<=n; ++k)
ins(i,j*n+k,,k*l);
ins(j*n+i,T,,);
}
ins(S,i,,);
}
}
int main(){
init();
printf("%.2lf",1.0*cost_flow(S,T)/n);
}

最新文章

  1. CocoaPods的安装、使用、以及遇到的问题
  2. 使用aggregate在MongoDB中查找重复的数据记录
  3. JSBinding+SharpKit / 脚本加密(JSC或Bytecode,参考cocos2d-js)
  4. 理解LoadRunner中的局部变量和全局变量
  5. python基础知识七
  6. 24种设计模式--多例模式【Multition Pattern】
  7. PHP迭代器
  8. MySQL学习笔记(4)
  9. 笔记7 AOP
  10. 约定Jenkins构建脚本
  11. AD软件使用心得
  12. vue的多选框
  13. C# 大型电商项目性能优化(一)
  14. Spring中 @Autowired标签与 @Resource标签 的区别(转)
  15. mysql replace into用法详细说明
  16. 【转】Vulhub - 开源的安全漏洞学习与复现项目
  17. win7 自带计算机(for programmer)
  18. LInux进程虚拟地址空间的管理
  19. cocos2dx 屏幕分辨率问题
  20. CodeChef CHEFSOC2 Chef and Big Soccer 水dp

热门文章

  1. 1013团队Beta冲刺day4
  2. 201621123062《java程序设计》第三周作业总结
  3. scrapy爬虫框架教程(二)-- 爬取豆瓣电影TOP250
  4. 【iOS】Swift GCD-下
  5. 项目Beta冲刺Day1
  6. win10 安装mingw ruby rails
  7. JavaScript简写技巧总结
  8. Django-rest-framework源码分析----认证
  9. JAVA_SE基础——3.Java程序的开发流程
  10. Python struct模块