同一时刻有 N N N位车主带着他们的爱车来到了汽车维修中心。
维修中心共有 M M M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。
现在需要安排这 M M M位技术人员所维修的车及顺序,使得顾客平均等待的时间 T T T最小。
说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
2 < = M < = 9 , 1 < = N < = 60 , 1 < = T < = 1000 2<=M<=9,1<=N<=60, 1<=T<=1000 2<=M<=9,1<=N<=60,1<=T<=1000
考虑建点
源 点 S 源点S 源点S 0 0 0 汇 点 T n + n ∗ m + m + 1 汇点T n+n*m+m+1 汇点Tn+n∗m+m+1
顾 客 顾客 顾客 1 1 1到 n n n 第 i 个 工 人 倒 数 第 j 个 修 n + n ∗ ( i − 1 ) + j 第i个工人倒数第j个修 n+n*(i-1)+j 第i个工人倒数第j个修n+n∗(i−1)+j
然后根据题意建一下模,
费用流然后结果/n即可
#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <cstdio>
#include <algorithm>
#define INF 0x3f3f3f3f
#define N 100005
#define M 1005
using namespace std;
struct Node { int To, num, cost, nxt; }e[N];
int incf[M], dis[M], pre[M], ls[M], v[M], n, m, C, S, T, cnt = 1;
int Max_flow = 0, Ans_cost = 0;
queue <int> Q;
void Addedge(int u, int v, int w, int f)
{
e[++cnt].To = v, e[cnt].num = w, e[cnt].cost = f, e[cnt].nxt = ls[u], ls[u] = cnt;
e[++cnt].To = u, e[cnt].num = 0, e[cnt].cost = -f, e[cnt].nxt = ls[v], ls[v] = cnt;
}
bool spfa(int s, int t)
{
for (int i = s; i <= t; i++) dis[i] = INF;
memset(v, 0, sizeof(v));
queue <int> Q;
while (Q.size()) Q.pop();
Q.push(s);
v[s] = 1; dis[s] = 0;
incf[s] = INF;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = ls[u]; i ; i = e[i].nxt)
if (e[i].num && dis[e[i].To] > dis[u] + e[i].cost)
{
incf[e[i].To] = min(incf[u], e[i].num);
dis[e[i].To] = dis[u] + e[i].cost;
pre[e[i].To] = i;
if (!v[e[i].To])
Q.push(e[i].To), v[e[i].To] = 1;
}
v[u] = 0;
}
return dis[t] != INF;
}
void update(int s, int t)
{
int x = t;
while (x != s)
{
int i = pre[x];
e[i].num -= incf[t];
e[i ^ 1].num += incf[t];
x = e[i ^ 1].To;
}
Max_flow += incf[t];
Ans_cost += dis[t] * incf[t];
}
void EK(int s, int t)
{
while (spfa(s, t)) update(s, t);
}
// 源点S 0 汇点T n+n*m+m+1
// 顾客 1~n 第i个工人倒数第j个修 n+n*(i-1)+j
int main()
{
scanf("%d %d", &m, &n);
S = 0, T = n + n * m + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
int cost; scanf("%d", &cost);
for (int k = 1; k <= n; k++) Addedge(i, n + n * (j - 1) + k, 1, k * cost);
}
for (int i = 1; i <= n; i++) Addedge(S, i, 1, 0);
for (int i = n + 1; i <= n + n * m; i++) Addedge(i, T, 1, 0);
EK(S, T);
printf("%.2lf\n", (double)((double)Ans_cost / (double)Max_flow));
return 0;
}
文章浏览阅读480次。http://blog.sina.com.cn/s/blog_736d0b9101018cgc.html_王斌 github
文章浏览阅读737次。原文来自:http://blog.csdn.net/hncqp/article/details/4455263 ACM OJ Collection(排名不分先后):中国:浙江大学(ZJU):http://acm.zju.edu.cn/北京大学(PKU):htt_htt//acm.wydtang.top/
文章浏览阅读467次。更新记录1.0.0(2019-07-01)插件简介专门用来修复苹果IOS支付时出现"您已购买此App内购买项目。此项目将免费恢复"。问题描述首先在IOS平台里面创建“APP内购买项目”,选择的是“消耗型项目”,然后用uni-app官方的支付api进行支付,多支付几次,有时候就会出现提示“您已购买此App内购买项目。此项目将免费恢复”,特别是在沙盒测试里面支付很大几率出现,我明明选的是消耗型项目,应..._ios开发苹果支付恢复权益
文章浏览阅读5.6k次。Spring从J2EE的Web端为每个关键接口提供了一个mock实现:MockHttpServletRequest几乎每个单元测试中都要使用这个类,它是J2EE Web应用程序最常用的接口HttpServletRequest的mock实现。MockHttpServletResponse此对象用于HttpServletRespons_mvcmock
文章浏览阅读8.5k次,点赞7次,收藏22次。execute as @a at @s run clear @s minecraft:dark_oak_planks{display:{Name:“{“text”:“第三关[阴森古堡]”,“color”:“red”,“italic”:false}”,color:“16711680”},Enchantments:[{id:“protection”,lvl:1}],Unbreakable:1b} 1。Lore:[“{“text”:“免费”,“color”:“blue”,“italic”:false}”]..._summon生成掉落物
文章浏览阅读10w+次,点赞487次,收藏2.1k次。CentOS 7安装教程: 准备: 软件:VMware Workstation 镜像文件:CentOS-7-x86_64-bin-DVD1.iso (附:教程较为详细,注释较多,故将操作的选项进行了加粗字体显示。) 1、文件--新建虚拟机--自定义 2、..._centos 安装
文章浏览阅读333次,点赞3次,收藏3次。项目介绍一款很好用的免费画图软件,支持ER图、时序图、流程图等等在项目的releases就可以下载最新版本同时支持在线编辑。_draw github画图
文章浏览阅读930次。嗨,大家好!如果你对人工智能充满了好奇,并且想要入门这个领域,那么你来对地方了。本文将向你介绍如何从零基础开始学习人工智能,并逐步掌握核心概念和技能。无论你是大学生、职场新人还是对人工智能感兴趣的任何人,都可以按照以下学习路径逐步提升自己。_人工智能学习路径
文章浏览阅读4.3k次,点赞2次,收藏8次。打开Unity3D的:window-asset store就会出来这样的界面:我们选择一个天空纹理,注意这里的标签只有一个,如果有多个就会显示所有标签的内容:找个比较小的免费的下载一下试试,比如这个:下载以后:点击import就会出现该窗口:然后再点击最底下的import:就导入到我们这里来了。从上面可以切换场景:..._unity怎么导入压缩包
文章浏览阅读254次。在你以前的问题的the answer的最后一部分,我试着给出你当前的问题的答案.也许我表示不够清楚.您不应该将错误信息放在标准成功响应中.您应该遵循用于服务器和客户端之间通信的HTTP协议的主要规则.根据HTTP协议实现网格中的加载数据,编辑行和与服务器的所有Ajax通信.每个HTTP响应都有响应第一行的状态代码.了解这个意义非常重要.典型的JSON数据成功请求如下HTTP/1.1 200 OK...._decode message error
文章浏览阅读4k次,点赞8次,收藏29次。我们在流片之后,通常还是有机会对layout进行局部小的修改。例如metal change eco或者一些层次的局部修改。当我们修改之后,需要进行与之前gds的对比,以便确认没有因为某些..._calibre dbdiff
文章浏览阅读694次。问题我有一些方法应该在某些输入上调用567779278。不幸的是,测试这些情况会导致JUnit终止!将方法调用放在新线程中似乎没有帮助,因为System.exit()终止了JVM,而不仅仅是当前线程。是否有任何常见的处理方式?例如,我可以将存根替换为System.exit()吗?[编辑]有问题的类实际上是一个命令行工具,我试图在JUnit中测试。也许JUnit根本不适合这份工作?建议使用互补回归测..._检查system.exit