2

私は自分の国で地元のプログラミング コンテストに参加したことがあります。コンテストの名前は「ACM-ICPC インドネシア ナショナル コンテスト 2013」です。
コンテストは 2013-10-13 15:00:00 (GMT +7) に終了しましたが、まだ問題の 1 つに興味があります。
問題の元のバージョンはここにあります。

簡単な問題の説明:
複数の「サーバー」(コンピューター) で実行する必要がある一連の「ジョブ」(タスク) があります。各ジョブは、開始時刻 S iから終了時刻 E i
まで 厳密に実行する必要があり ます。各サーバーは一度に 1 つのタスクしか実行できません。 (複雑なことはここにあります) サーバーがあるジョブから別のジョブに切り替わるには、ある程度の時間がかかります。 サーバーがジョブ J xを終了した場合、ジョブ J yを開始するには、ジョブ J xの完了後に休憩時間 T x,yが必要になります。これは、サーバーがジョブ J xをクリーンアップしてジョブ J yをロードするのに必要な時間です。 つまり、ジョブ J y



E x + T x,y ≤ S yの場合に限り、ジョブ J xの後に実行できます。

問題は、すべてのジョブを実行するために必要なサーバーの最小数を計算することです。

例:
たとえば、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はテスト ケースの数、次にジョブの数 (2 番目3はケース 1 に 3 つのジョブがあることを意味します)、次に E iと S i、T 行列 (サイズが等しい)です。ジョブの数)。 

3
3
3 6
10 15
16 20
0 2 5
0 0 3
0 0 0
4
8 10
4 7
12 15
1 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
4
8 10
4 7
12 15
1 4
0 50 50 50
50 0 50 50
50 50 0 50
50 50 50 0

サンプル出力: 

ケース #1: 2
ケース #2: 1
ケース #3: 4

感想：
所要時間はグラフ行列で表現できるので有向非巡回グラフ問題と推測しています。
私がこれまでに試した方法は力ずくで貪欲ですが、間違った答えが得られました。(残念ながら、私はもうコードを持っていません)
おそらく動的プログラミングでも解決できますが、よくわかりません。
この問題を解決する方法について、私は本当に明確な考えを持っていません。
したがって、簡単なヒントや洞察は私にとって非常に役立ちます。

4

1 に答える 1

3

これは、二部グラフの最大一致を計算することで解決できます。

アイデアは、ジョブの終了時刻とジョブの開始時刻を一致させようとしているということです。

一致した終了時刻 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-18T17:54:46.973 に答える