在编程竞赛中需要关于问题集的帮助

我参加了我的国家的本地编程比赛。比赛的名称是“ACM-ICPC 2013年全国比赛”。
比赛已于2013-10-13 15:00:00（格林威治标准时间+7）结束，我仍然对其中一个问题感到好奇。
你可以找到问题的原始版本here。在编程竞赛中需要关于问题集的帮助

简要说明问题：
有，应该在几个“服务器”（计算机）进行一组“工作”（任务）中。
每个作业应严格从开始时间S _我执行结束时间E _我
每个服务器只能一次执行一个任务。
（复杂的事情发生在这里）服务器从一个工作切换到另一个需要一些时间。
如果一台服务器完成工作j _X，然后开始工作j _Ÿ它需要一个中场休息时间T _X，Y工作j之后_X完成。这是服务器清理作业所需的时间J _x和加载作业J _y。
换句话说，工作j _ý可以工作j之后运行_X当且仅如果E _X + T _的x，y≤小号_ÿ。

问题是要计算完成所有工作所需的最少服务器数量。

例子：
例如，让有3个项目

S(1) = 3 and E(1) = 6 
S(2) = 10 and E(2) = 15 
S(3) = 16 and E(3) = 20 
T(1,2) = 2, T(1,3) = 5 
T(2,1) = 0, T(2,3) = 3 
T(3,1) = 0, T(3,2) = 0

在这个例子中，我们需要2台服务器：

Server 1: J(1), J(2) 
Server 2: J(3)

样品输入：
短解释：第一个3是测试用例的数量，其次是作业数量（第二个3意味着对于情况1有3个作业），然后是E _i和S _i，则T矩阵（大小等于数量工作）。

样本输出：

Case #1: 2 
Case #2: 1 
Case #3: 4

个人评论：
可以被表示为图矩阵所需要的时间，所以我假定这是一个向无环图的问题。
我到目前为止尝试的方法是蛮力和贪婪，但得到了错误的答案。（不幸的是我没有我的代码了）
也许可以通过动态编程来解决，但我不确定。
我真的不清楚如何解决这个问题。
所以一个简单的提示或洞察力将对我非常有帮助。

来源

2013-10-18 topher

我是比较新的堆栈溢出。我想问一下这样的问题是不恰当的还是被认为是偏离主题的。 – topher

您是否试图将此模型作为最大流量最小成本问题进行建模？ - 我相信这是要走的路。 – Skeen

@Skeen，谢谢你的见解，我以前没有尝试过.. – topher

你可以通过计算maximum matching in a bipartite graph来解决这个问题。

这个想法是你试图将工作结束时间与工作开始时间相匹配。

匹配的结束时间x与开始时间y意味着相同的服务器将执行作业x和作业y。

您需要的服务器数量将对应于不匹配的开始时间的数量（因为这些作业中的每一个都需要新的服务器）。使用NetworkX

例Python代码：

import networkx as nx 
G=nx.DiGraph() 

S=[3,10,16] # start times 
E=[6,15,20] # end times 
T = [ [0, 2, 5], 
     [0, 0, 3], 
     [0, 0, 0] ] # T[x][y] 
N=len(S) 

for jobx in range(N): 
    G.add_edge('start','end'+str(jobx),capacity=1) 
    G.add_edge('start'+str(jobx),'end',capacity=1) 
    for joby in range(N): 
     if E[jobx]+T[jobx][joby] <= S[joby]: 
      G.add_edge('end'+str(jobx),'start'+str(joby),capacity=1) 

print N-nx.max_flow(G,'start','end')

来源

2013-10-18 17:54:46

在编程竞赛中需要关于问题集的帮助

回答

相关问题