网络流/费用流


  好神奇的建模= =

关键就是把每个技术员拆成n个点,表示这个技术员倒数第几个修的车子。。

考虑第i个工人,他修第j辆车只对后面要修的车有影响,而前面修过的车已经对当前没有影响了。
而这个影响就是后面每个将要修理的车都多等待了time的时间。

说一下我的思考过程吧:(好混乱……)

  对于每辆车只修一次,所以每辆车跟S连(1,0)边(表示流量为1,费用为0)。

  然后每辆车的修车时间怎么算呢?每辆车都跟每个修理工连边,这是肯定的……但是还有等待啊,等待的时间怎么算呢?

  倒过来考虑,假如我们现在有一个修理方案,修理工A的修理顺序是1、2、4、6、7,那么他修1号车对于总等待时间的贡献就是time[1][A]*5,因为后面四辆车还得等着嘛;以此类推,修4号车的cost为time[4][A]*3……即倒数第 j 辆车的修理时间cost为time[car[j]][A]*j

  已知了修理方案我们怎么用费用流的模型来表示出来它呢?

  我们可以把每个修理工拆开!将一个修理工拆成n个点,第 j 个点表示这个修理工按序修的倒数第 j 辆车,由这个点连向所有车,流量为1,cost就为time[ 这辆车 ][ 这个修理工 ]*j,那么刚刚的例子中,第1号车就连向了修理工A的倒数第5个点,2号车连着倒数第4个点……

  如果最优方案中A修的车没有5辆?而是1、4、7?那第一辆车肯定就不会去连倒数第5个点了,因为是最小费用流嘛,它就会连到倒数第3个点,4号车就会连到倒数第二个点……

  这样建图,其实是把所有的方案都枚举了出来,每种修理方案都对应着一个流!

UPD:2015-03-19 09:22:15

  VFK:裸的二分图最小权匹配,用KM来写会更快……

 /**************************************************************
Problem: 1070
User: Tunix
Language: C++
Result: Accepted
Time:464 ms
Memory:6012 kb
****************************************************************/ //BZOJ 1070
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=,INF=~0u>>;
const double eps=1e-;
/*******************template********************/
int n,m,ans,tim[][];
struct edge{int from,to,v,c;};
struct Net{
edge E[M];
int head[N],next[M],cnt;
void ins(int x,int y,int z,int c){
E[++cnt]=(edge){x,y,z,c};
next[cnt]=head[x]; head[x]=cnt;
}
void add(int x,int y,int z,int c){
ins(x,y,z,c); ins(y,x,,-c);
}
int from[N],Q[M],S,T,d[N];
bool inq[N];
bool spfa(){
int l=,r=-;
F(i,S,T) d[i]=INF;
d[S]=; Q[++r]=S; inq[S]=;
while(l<=r){
int x=Q[l++];
inq[x]=;
for(int i=head[x];i;i=next[i])
if (E[i].v && d[x]+E[i].c<d[E[i].to]){
d[E[i].to]=d[x]+E[i].c;
from[E[i].to]=i;
if(!inq[E[i].to]){
Q[++r]=E[i].to;
inq[E[i].to]=;
}
}
}
return d[T]!=INF;
}
void mcf(){
int x=INF;
for(int i=from[T];i;i=from[E[i].from])
x=min(x,E[i].v);
for(int i=from[T];i;i=from[E[i].from]){
E[i].v-=x;
E[i^].v+=x;
ans+=x*E[i].c;
}
// ans+=x*d[t];
}
void init(){
m=getint(); n=getint(); cnt=;
F(i,,n)
F(j,,m) tim[i][j]=getint();
S=; T=n+n*m+;
F(i,,n) add(S,i,,);
F(i,n+,n+n*m) add(i,T,,);
F(i,,n)
F(j,,m)
F(k,,n)//枚举这 第i辆车是第j个人修的第k辆
add(i,j*n+k,,(n-k+)*tim[i][j]);
ans=;
while(spfa()) mcf();
printf("%.2lf\n",double(ans)/n);
}
}G1;
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
G1.init();
return ;
}

1070: [SCOI2007]修车

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 3044  Solved: 1227
[Submit][Status][Discuss]

Description


一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M
位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。 说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

Input

第一行有两个m,n,表示技术人员数与顾客数。 接下来n行,每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。

Output

最小平均等待时间,答案精确到小数点后2位。

Sample Input

2 2
3 2
1 4

Sample Output

1.50

HINT

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

Source

[Submit][Status][Discuss]

最新文章

  1. Java学习笔记 07 接口、继承与多态
  2. Particles.js基于Canvas画布创建粒子原子颗粒效果
  3. (C++) 基本面试题(整理)
  4. Winform使用DevExpress的WaitDialogForm画面 z
  5. MySQL 列子查询及 IN、ANY、SOME 和 ALL 操作符的使用(转)
  6. Java - 字符串和Unicode互转 - 解析小米pm.min.js
  7. IOS开发-UI学习-UIPageControl(页码控制器)的使用
  8. (转)Centos7 Nginx安装
  9. RxJava整合Retrofit遇到的问题总结
  10. 【转载】C#中自定义Sort的排序规则IComparable接口
  11. 笔记《JavaScript 权威指南》(第6版) 分条知识点概要3—表达式和运算符
  12. auto关键字
  13. Unity3d跨平台原理
  14. KMP字符串匹配算法理解(转)
  15. Total Commander如何设置自定义快捷键在当前目录打开ConEmu
  16. TensorFlow—多层感知器—MNIST手写数字识别
  17. Python爬虫爬取豆瓣电影之数据提取值xpath和lxml模块
  18. php jsonp实例 mip无限滚动组件接口注意事项
  19. php实现二维码
  20. 判断vps类型

热门文章

  1. C# 关于委托和事件的妙文
  2. Android四大组件之一:BroadCastReceiver(广播接收者)
  3. C++调用GDAL库读取并输出tif文件,并计算斑块面积输出景观指数:CSD
  4. 引入OO开发报表后的感想
  5. C# 枚举操作扩展类
  6. Oracle 创建用户授权
  7. Css background缩写
  8. U-Boot--配置过程分析
  9. 基础学习总结(四)---内存获取、XML之PULL解析
  10. 【Qt】命令行编译Qt程序(nmake)【转】