【网络流】【BZOJ1070】【SCOI2007】修车
2024-08-24 03:12:22
原题链接: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);
}
最新文章
- CocoaPods的安装、使用、以及遇到的问题
- 使用aggregate在MongoDB中查找重复的数据记录
- JSBinding+SharpKit / 脚本加密(JSC或Bytecode,参考cocos2d-js)
- 理解LoadRunner中的局部变量和全局变量
- python基础知识七
- 24种设计模式--多例模式【Multition Pattern】
- PHP迭代器
- MySQL学习笔记(4)
- 笔记7 AOP
- 约定Jenkins构建脚本
- AD软件使用心得
- vue的多选框
- C# 大型电商项目性能优化(一)
- Spring中 @Autowired标签与 @Resource标签 的区别(转)
- mysql replace into用法详细说明
- 【转】Vulhub - 开源的安全漏洞学习与复现项目
- win7 自带计算机(for programmer)
- LInux进程虚拟地址空间的管理
- cocos2dx 屏幕分辨率问题
- CodeChef CHEFSOC2 Chef and Big Soccer 水dp