题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1070

需要考虑前面修的车对后面等待的车造成的时间增加;

其实可以从每个人修车的顺序考虑,如果这辆车作为最后一辆被一个人修,那么它对后面的车无影响,而每提前一位,影响时间就增加一份;

也就是如果确定一辆车是第几个被修的,那么它的影响就可以单独确定;

费用流的选边策略是先选费用小的,再选费用大的,正可以对应这个过程;

所以把每个人拆成 n 个点表示修车顺序,然后车向对应的点连对应边权的边即可。

代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int const xn=,xm=,inf=1e9;
int n,m,hd[xn],ct=,to[xm],nxt[xm],w[xm],c[xm],S,T;
int dis[xn],pre[xn],inc[xn];
bool vis[xn];
queue<int>q;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int Min(int x,int y){return x<y?x:y;}
void ade(int x,int y,int z,int f){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; w[ct]=z; c[ct]=f;}
void add(int x,int y,int z,int f){ade(x,y,z,f); ade(y,x,-z,);}
int id(int x,int tp)
{
if(!tp)return m*n+x;
return (x-)*n+tp;
}
bool bfs()
{
for(int i=S;i<=T;i++)vis[i]=;
for(int i=S;i<=T;i++)dis[i]=inf;
dis[S]=; q.push(S); vis[S]=; inc[S]=inf;//inc!!
while(q.size())
{
int x=q.front(); q.pop(); vis[x]=;
for(int i=hd[x],u;i;i=nxt[i])
if(dis[u=to[i]]>dis[x]+w[i]&&c[i])
{
dis[u]=dis[x]+w[i]; pre[u]=i;
inc[u]=Min(inc[x],c[i]);
if(!vis[u])vis[u]=,q.push(u);
}
}
return dis[T]!=inf;
}
void up()
{
int x=T;
while(x!=S)
{
int i=pre[x];
c[i]-=inc[T]; c[i^]+=inc[T];
x=to[i^];
}
}
int main()
{
m=rd(); n=rd(); S=; T=id(n,)+;
for(int j=;j<=n;j++)
for(int i=,x;i<=m;i++)
{
x=rd();
for(int k=;k<=n;k++)
add(id(j,),id(i,k),k*x,);
}
for(int j=;j<=n;j++)add(S,id(j,),,);
for(int i=id(,);i<=id(m,n);i++)add(i,T,,);
int ans=;
while(bfs())ans+=dis[T]*inc[T],up();
printf("%.2f\n",1.0*ans/n);
return ;
}

最新文章

  1. JavaScript之链式结构序列化
  2. 机器指令翻译成 JavaScript —— No.5 指令变化
  3. HTML5 -入门 (---css样式-------------(css基础与css选择器)---------------------—)
  4. post请求接口
  5. LR工具使用之结果分析
  6. SQL 面试题(一)
  7. cocos2d-x3.0-结合TH脚本引擎
  8. jquery ajax 局部table 刷新技术
  9. Mac上使用Visual Studio Code开发/调试.NET Core代码
  10. CodeForces 678C Joty and Chocolate
  11. VS 测试printf 多参数 输出 i++ 和++i 结果
  12. Recurrent Neural Networks(RNN) 循环神经网络初探
  13. java 实现文件上传下载以及查看
  14. 从零开始学spring cloud(九) -------- 超时机制,断路器模式介绍
  15. Numpy求均值、中位数、众数的方法
  16. hadoop 2.7.1安装和配置
  17. mysql千万级数据库插入速度和读取速度的调整记录
  18. LCA tarjan+并查集POJ1470
  19. 【python】理想论坛帖子爬虫1.06
  20. HTTP Client Performance Improvements

热门文章

  1. centos6安装nginx最详细步骤
  2. Java内部类(转发:)
  3. python3 pillow使用测试
  4. linux mount一个硬盘
  5. NSAttributedStringKey
  6. 每天一个Linux命令(35)wc命令
  7. Data Structure Binary Tree: Convert an arbitrary Binary Tree to a tree that holds Children Sum Property
  8. Idea 包名按树形结构展示
  9. PHP中include路径的解决方法汇总
  10. Android Studio 技巧备忘