ハンガリーアルゴリズム

ハンガリー法は、割り当て問題を多項式時間で解く組み合わせ最適化 アルゴリズムであり、後の主双対法の先駆けとなった。このアルゴリズムは、1955年にハロルド・クーンによって開発され、公開された。このアルゴリズムは、ハンガリーの数学者であるデーネス・ケーニヒとイェネー・エゲルヴァーリの初期の業績に大きく基づいていたため、クーンはこのアルゴリズムに「ハンガリー法」という名前をつけた。^{[1] [2]}しかし、2006年に、カール・グスタフ・ヤコビが19世紀に割り当て問題を解いており、その解法はヤコビの死後、1890年にラテン語で出版されていたことが発覚した。^[3]

ジェームズ・マンクレス氏は1957年にこのアルゴリズムをレビューし、それが（強く）多項式であることに気づきました。^{[4]それ以来、このアルゴリズムは}、クーン・マンクレスアルゴリズムまたはマンクレス割り当てアルゴリズムとしても知られています。元のアルゴリズムの時間計算量は でしたが、エドモンズとカープ、そして独立に富澤は、実行時間 を達成するように変更できることに気付きました。^{[5] [6]}フォードとフルカーソンは、フォード・フルカーソンアルゴリズムの形で、この方法を一般的な最大フロー問題に拡張しました。 ${\displaystyle O(n^{4})}$${\displaystyle O(n^{3})}$

この単純な例では、アリス、ボブ、キャロルという 3 人の労働者がいます。1 人はバスルームを掃除し、もう 1 人は床を掃き、3 人目は窓を拭く必要がありますが、各作業に対してそれぞれ異なる報酬を要求します。問題は、最も低コストで作業を割り当てる方法を見つけることです。この問題は、作業を行う労働者のコストのマトリックスで表すことができます。例:

ハンガリー方式を上記の表に適用すると、最小コストが算出されます。これは 15 ドルで、アリスに浴室を掃除させ、キャロルに床を掃き、ボブに窓を洗わせることで達成されます。これは、ブルート フォースを使用して確認できます。

（担当外の人が窓を洗う）

行列の定式化では、 n × n 行列が与えられます。ここで、 i行目とj列目の要素は、j番目のジョブをi番目の労働者に割り当てるコストを表します。各ジョブが 1 人の労働者に割り当てられ、各労働者に 1 つのジョブが割り当てられるように、割り当ての合計コストが最小になるように、労働者へのジョブの割り当てを見つける必要があります。

これは、コスト行列Cの行を並べ替えて行列の トレースを最小化することで表現できます。

${\displaystyle \min _{P}\operatorname {Tr} (PC)\;,}$

ここで、P は順列行列です。 (同様に、列はCP を使用して順列化できます。)

最大コストをもたらす割り当てを見つけることが目標である場合、コスト行列C を否定することで問題を解決できます。

このアルゴリズムは、二部グラフを使用して問題を定式化することで同等に記述できます。n個のワーカー頂点 ( S ) とn 個のジョブ頂点 ( T )を持つ完全な二部グラフ があり、各エッジ ( E ) にはコストがあります。最小の総コストで完全なマッチングを見つけたいのです。 ${\displaystyle G=(S,T;E)}$${\displaystyle c(i,j)}$

各 に対してとなる関数をポテンシャルと呼びます。 ${\displaystyle y:(S\cup T)\to \mathbb {R} }$${\displaystyle y(i)+y(j)\leq c(i,j)}$${\displaystyle i\in S,j\in T}$

ポテンシャルyの値は、すべての頂点のポテンシャルの合計です。

${\displaystyle \sum _{v\in S\cup T}y(v)}$。

各完全マッチングのコストは、少なくとも各ポテンシャルの値です。マッチングの合計コストは、すべてのエッジのコストの合計です。各エッジのコストは、少なくともそのエンドポイントのポテンシャルの合計です。マッチングは完全であるため、各頂点は正確に 1 つのエッジのエンドポイントです。したがって、合計コストは、少なくとも合計ポテンシャルです。

ハンガリアン法は、マッチングコストがポテンシャル値に等しいような完全マッチングとポテンシャルを見つけます。これは、両方が最適であることを証明します。実際、ハンガリアン法はタイトエッジの完全マッチングを見つけます。つまり、 の場合、エッジはポテンシャルyに対してタイトであると呼ばれます。タイトエッジのサブグラフを で表します。 における完全マッチングのコスト(存在する場合)は、の値に等しくなります。 ${\displaystyle ij}$${\displaystyle y(i)+y(j)=c(i,j)}$${\displaystyle G_{y}}$${\displaystyle G_{y}}$

アルゴリズムの実行中、潜在的な yと、TからSに向いたエッジがマッチングM を形成するという特性を持つの向き( で示される) を維持します。最初は、yはどこでも 0 で、すべてのエッジはSからTに向い(つまりMは空) ています。各ステップでは、 yの値を増やすように変更するか、より多くのエッジを持つマッチングを取得するように向きを変更します。M のすべてのエッジがタイトであるという不変条件を維持します。Mが完全なマッチング であれば完了です。${\displaystyle G_{y}}$${\displaystyle {\overrightarrow {G_{y}}}}$

一般的なステップでは、およびをMでカバーされていない頂点とします（したがって、は入ってくるエッジを持たないSの頂点で構成され、出ていくエッジを持たないTの頂点で構成されます）。Zを、有向パスによってからに到達可能な頂点の集合とします。これは、幅優先探索によって計算できます。 ${\displaystyle R_{S}\subseteq S}$${\displaystyle R_{T}\subseteq T}$${\displaystyle R_{S}}$${\displaystyle R_{T}}$${\displaystyle {\overrightarrow {G_{y}}}}$${\displaystyle R_{S}}$

が空でない場合は、からまでの有向パスに沿ったすべてのエッジの向きを反転します。したがって、対応するマッチングのサイズは 1 増加します。 ${\displaystyle R_{T}\cap Z}$${\displaystyle {\overrightarrow {G_{y}}}}$${\displaystyle R_{S}}$${\displaystyle R_{T}}$

が空の 場合は、${\displaystyle R_{T}\cap Z}$

${\displaystyle \Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}.}$

Δ は、マッチングがまだ最大可能サイズに達していない場合は常に、少なくとも 1 つのそのようなエッジが存在する必要があるため、明確に定義されます(次のセクションを参照)。と の間にはタイト エッジがないため、 は正です。の頂点でy をΔだけ増やし、の頂点でy をΔだけ減らします。結果のyは依然としてポテンシャルであり、グラフは変化しますが、依然としてM が含まれています (次のサブセクションを参照)。新しいエッジをSからTに向けます。 Δの定義により、から到達可能な頂点の集合Zが増加します (タイト エッジの数は必ずしも増加しないことに注意してください)。 ${\displaystyle ij}$${\displaystyle Z\cap S}$${\displaystyle T\setminus Z}$${\displaystyle Z\cap S}$${\displaystyle Z\cap T}$${\displaystyle G_{y}}$${\displaystyle R_{S}}$

M が完全に一致するまでこれらの手順を繰り返します。完全に一致すると、最小コストの割り当てが行われます。このバージョンの方法の実行時間は次のとおりです。Mはn回増加し、 Mが変更されないフェーズでは、最大でn 回の潜在的な変更があります( Z が毎回増加するため)。潜在的な変更に十分な時間は です。 ${\displaystyle O(n^{4})}$${\displaystyle O(n^{2})}$

マッチングが最大可能サイズでない限り、アルゴリズムは常に進行できること、つまり、一致するエッジの数を増やすか、少なくとも 1 つのエッジを狭くできることを示さなければなりません。各ステップで少なくとも次のいずれかが当てはまることを示せば十分です。

• Mは最大サイズです。
• ${\displaystyle G_{y}}$拡張パスが含まれています。
• Gには、ルーズテールパスが含まれます。これは、 内のいずれかの頂点から内の頂点までのパスで、任意の数 (ゼロの場合もある) のタイトエッジと、それに続く 1 つのルーズエッジで構成されます。ルーズテールパスの最後のルーズエッジは からであり、 Δが明確に定義されていることを保証します。${\displaystyle R_{S}}$${\displaystyle T\setminus Z}$${\displaystyle Z\cap S}$

M が最大サイズであれば、もちろんこれで終わりです。そうでない場合、Berge の補題により、基礎となるグラフGにおいてMに関する増加パスP が存在する必要があります。ただし、このパスは には存在しない可能性があります。Mの定義により、 Pのすべての偶数エッジはタイトですが、奇数エッジはルーズであるため には存在しない可能性があります。P の一方の端点は にあり、もう一方の端点は にあります。たとえば、 で始まるとします。P のすべてのエッジがタイトであれば、それは 内の増加パスのままとなり、これで終わりです。そうでない場合、 を P 上の最初のルーズなエッジとします。そうであれば、ルーズテールのパスが見つかったことになり、これで終わりです。そうでない場合、v は内の頂点からのタイトなエッジの別のパスQから到達可能です。をvから始まり最後まで続くPのサブパスとし、 を上の頂点に達するまでQに沿って移動し、次に の最後まで続くことで形成されるパスとします。は、 G内の増加パスであり、 Pよりも緩いエッジが少なくとも 1 つ少ないことに注目してください。Pは に置き換えることができ、この推論プロセスは、 G 内の増加パスまたはG内の緩いテール パスのいずれかが見つかる まで繰り返されます (正式には、緩いエッジの数に関する帰納法を使用) 。${\displaystyle G_{y}}$${\displaystyle G_{y}}$${\displaystyle R_{S}}$${\displaystyle R_{T}}$${\displaystyle R_{S}}$${\displaystyle G_{y}}$${\displaystyle uv}$${\displaystyle v\notin Z}$${\displaystyle R_{S}}$${\displaystyle P_{v}}$${\displaystyle P'}$${\displaystyle P_{v}}$${\displaystyle P_{v}}$${\displaystyle P'}$${\displaystyle P'}$${\displaystyle G_{y}}$

M内のすべての辺がy を調整した後も残ることを示すには、 M内の任意の辺について、その両端点の両方がZにないか、どちらも Z にないかのどちらかであることを示すだけで十分です。このために、M内のTからSへの辺をとします。 M内のすべての辺はタイトであるため、 vがZにあればu もZ になければならないことは容易にわかります。ここで、矛盾するようですが、しかしu自体は、一致する辺の端点であるために存在することはできないと仮定します。そのため、 u 内の頂点からuへのタイトな辺の有向パスが存在する必要があります。このパスはv を避ける必要があります。なぜなら、仮定によりv はZに存在しないため、このパスでu の直前の頂点は別の頂点です。はTからSへのタイトな辺であるため、Mに存在します。しかし、Mには頂点u を共有する 2 つの辺が含まれるため、 Mがマッチングしているという事実と矛盾します。したがって、 M内のすべての辺は、両端点が Z にあるか、どちらの端点もZに存在しないかのどちらかです。 ${\displaystyle vu}$${\displaystyle u\in Z}$${\displaystyle v\notin Z}$${\displaystyle R_{S}}$${\displaystyle R_{S}}$${\displaystyle v'\in T}$${\displaystyle v'u}$

yが調整後も潜在的可能性を維持することを示すには、どのエッジもそのコストを超えて潜在的可能性の総量が増加しないことを示すだけで十分です。これは前の段落でMのエッジについてすでに確立されているので、 SからTへの任意のエッジuvを考えてみましょう。 がΔだけ増加すると、 （この場合 はΔだけ減少してエッジの潜在的可能性の総量は変化しない）または （この場合Δの定義によりが保証される）のいずれかになります。したがって、は潜在的可能性を維持します。 ${\displaystyle y(u)}$${\displaystyle v\in Z\cap T}$${\displaystyle y(v)}$${\displaystyle v\in T\setminus Z}$${\displaystyle y(u)+y(v)+\Delta \leq c(u,v)}$

ジョブとワーカー ( )があるとします。ジョブの各プレフィックスについて、これらのジョブをそれぞれ異なるワーカーに割り当てるための最小の合計コストを計算する方法について説明します。具体的には、番目のジョブを追加し、時間 で合計コストを更新して、全体の時間計算量は になります。これは、ジョブの数がワーカーの数に比べて少ない場合 よりも優れていることに注意してください。${\displaystyle J}$${\displaystyle W}$${\displaystyle J\leq W}$${\displaystyle j}$${\displaystyle O(jW)}$${\displaystyle O\left(\sum _{j=1}^{J}jW\right)=O(J^{2}W)}$${\displaystyle O(W^{3})}$

前のセクションと同じ表記法を使用しますが、必要に応じて定義を変更します。 は最初のジョブの集合を表し、 はすべてのワーカーの集合を表します。 ${\displaystyle S_{j}}$${\displaystyle j}$${\displaystyle T}$

アルゴリズムのステップの前に、内のすべてのジョブとポテンシャルに一致する のマッチングがあり、次の条件を満たすと仮定します。マッチングはポテンシャルに関してタイトであり、すべてのマッチングされていないワーカーのポテンシャルはゼロであり、すべてのマッチングされたワーカーのポテンシャルは非正です。このようなポテンシャルは、マッチングの最適性を証明することに注意してください。 ${\displaystyle j}$${\displaystyle S_{j-1}\cup T}$${\displaystyle S_{j-1}}$${\displaystyle y}$

番目のステップでは、番目のジョブを に追加してを形成し、初期化します。常に、内のすべての頂点は の 番目のジョブから到達可能です。 にはジョブが割り当てられていないワーカーが含まれていませんが、 ${\displaystyle j}$${\displaystyle j}$${\displaystyle S_{j-1}}$${\displaystyle S_{j}}$${\displaystyle Z=\{j\}}$${\displaystyle Z}$${\displaystyle j}$${\displaystyle G_{y}}$${\displaystyle Z}$

${\displaystyle \Delta :=\min\{c(j,w)-y(j)-y(w):j\in Z\cap S_{j},w\in T\setminus Z\}}$

および は、最小値が得られる任意の値を表します。前のセクションで説明した方法でポテンシャルを調整すると、 からへのタイトエッジが作成されます。 ${\displaystyle w_{\text{next}}}$${\displaystyle w}$${\displaystyle Z}$${\displaystyle w_{\text{next}}}$

• が一致しない場合は、から へのタイトエッジのサブグラフに増加パスがあります。このパスに沿ってマッチングを切り替えると、最初のジョブが一致し、この手順は終了します。${\displaystyle w_{\text{next}}}$${\displaystyle j}$${\displaystyle w_{\text{next}}}$${\displaystyle j}$
• それ以外の場合は、とそれに一致するジョブを に追加します。${\displaystyle w_{\text{next}}}$${\displaystyle Z}$

ポテンシャルの調整には時間がかかります。ポテンシャルとを変更した後で、とを再計算することも、時間内に実行できます。ケース 1 は、ケース 2 が発生して手順が終了する前に、最大で回発生する可能性があり、全体的な時間計算量は になります。 ${\displaystyle O(W)}$${\displaystyle \Delta }$${\displaystyle w_{\text{next}}}$${\displaystyle Z}$${\displaystyle O(W)}$${\displaystyle j-1}$${\displaystyle O(jW)}$

実装の便宜上、以下のコードでは、これまでに計算されたすべての合計の否定を格納する追加のワーカーを追加します。番目のジョブが追加され、マッチングが更新されると、現在のマッチングのコストは、これまでに計算されたすべての合計、つまり に等しくなります。 ${\displaystyle w_{W}}$${\displaystyle y(w_{W})}$${\displaystyle \Delta }$${\displaystyle j}$${\displaystyle \Delta }$${\displaystyle -y(w_{W})}$

このコードはe-maxx :: algoから改変したものです。^[7]

/**
* ハンガリー語を使用した https://open.kattis.com/problems/cordonbleu の解答
* アルゴリズム。
*/

#include <cassert> 
#include <iostream> 
#include <制限> 
#include <ベクター> 
名前空間std を使用します。  

/**
* a = min(a, b) を設定します。
* b < a の場合は true を返す
*/
テンプレート< class T > bool ckmin ( T & a , const T & b ) { return b < a ? a = b , 1 : 0 ; }                     

/**
* J個のジョブとW個のワーカー（J <= W）が与えられた場合、各ジョブを割り当てるための最小コストを計算します。
* 個別のワーカーへのジョブのプレフィックス。
*
* @tparam T Jのオーダーの整数を表すのに十分な大きさの型 *
* 最大値(|C|)
* @param C 次元 JxW の行列。C[j][w] = j番目を割り当てるコスト
* ジョブを w 番目のワーカーに渡す (負の値になる可能性あり)
*
* @return 長さJのベクトル。j番目の要素は最小コストに等しい
* 最初の（j+1）個のジョブを別々のワーカーに割り当てる
*/
テンプレート< class T > vector < T > hungarian ( const vector < vector < T >> & C ) {       
    定数int J = ( int ) size ( C )、W = ( int ) size ( C [ 0 ] )。       
    アサート( J <= W );  
    // job[w] = w番目のワーカーに割り当てられたジョブ、またはジョブが割り当てられていない場合は-1
    // 注: 便宜上、W 番目のワーカーが追加されました
    ベクトル< int >ジョブ( W + 1 , -1 );    
    ベクトル< T > ys ( J ), yt ( W + 1 ); // ポテンシャル      
    // -yt[W]はすべてのデルタの合計に等しくなります
    ベクトル<T>の答え;​ 
    const T inf = numeric_limits < T >:: max ();    
    for ( int j_cur = 0 ; j_cur < J ; ++ j_cur ) { // j_cur番目のジョブを割り当てる           
        w_cur はW の整数値です。   
        ジョブ[ w_cur ] = j_cur ;  
        // Z からワーカー w までのエッジの最小削減コスト
        ベクトル<T> min_to ( W + 1 , inf ) ;​    
        vector < int > prv ( W + 1 , -1 ); // 交互パス上の前のワーカー      
        vector < bool > in_Z ( W + 1 ); // ワーカーが Z 内にあるかどうか       
        while ( job [ w_cur ] != -1 ) { // 最大で j_cur + 1 回実行される       
            in_Z [ w_cur ] = true ;  
            定数int j =ジョブ[ w_cur ];    
            Tデルタ= inf ;   
            w_next ;​ 
            ( int w = 0 ; w < W ; ++ w ) {​         
                if ( ! in_Z [ w ]) {  
                    ckmin ( min_to [ w ], C [ j ][ w ] - ys [ j ] - yt [ w ] )の場合      
                        prv [ w ] = w_cur ;  
                    ckmin ( delta , min_to [ w ])の場合、w_next = w ;     
                }
            }
            // デルタは常に非負になります。
            // このループが最初に実行されるときを除く
            // C[j_cur]のいずれかのエントリが負の場合
            ( int w = 0 ; w < = W ; ++ w ) {         
                in_Z [ w ] の場合、ys [ job [ w ]] += delta 、yt [ w ] -= delta ;       
                そうでない場合、min_to [ w ] -= delta ;   
            }
            w_cur = w_next ;  
        }
        // 交互パスに沿って割り当てを更新します
        for ( int w ; w_cur != W ; w_cur = w )ジョブ[ w_cur ] =ジョブ[ w = prv [ w_cur ]];             
        回答.push_back ( -yt [ W ] ) ;
    }
    回答を返す; 
}

/**
* 健全性チェック: https://en.wikipedia.org/wiki/Hungarian_algorithm#Example
* 最初の仕事（5）：
* バスルームをきれいにする: ボブ -> 5
* 第一職＋第二職（9）：
* バスルームをきれいにする: ボブ -> 5
* フロアを掃除する: アリス -> 4
* 第一職＋第二職＋第三職（15）：
* バスルームをきれいにする: アリス -> 8
* 床掃除: キャロル -> 4
* 窓を洗う: ボブ -> 3
*/
void sanity_check_hungarian () {  
    ベクトル<ベクトル< int >>コスト{{ 8 , 5 , 9 }, { 4 , 2 , 4 }, { 7 , 3 , 8 }};         
    assert ((ハンガリアン(コスト) ==ベクトル< int > { 5 , 9 , 15 }));    
    cerr << "正常性チェックに合格しました。\n " ;  
}

// https://open.kattis.com/problems/cordonbleu を解決します
voidコルドンブルー() {  
    整数N , M ;  
    cin >> N >> M ;    
    ベクトル<ペア< int 、int >> B ( N )、C ( M );   
    ベクトル<ペア< int 、int >>ボトル( N )、宅配便( M );   
    for ( auto & b :ボトル) cin >> b . first >> b . second ;         
    for ( auto & c : couriers ) cin >> c . first >> c . second ;         
    ペア< int , int >残り;  
    cin >>残り.最初>>残り. 2 番目;    
    ベクトル<ベクトル< int >>コスト( N 、ベクトル< int > ( N + M - 1 ));      
    自動分散= [ & ](ペア< int 、int > x 、ペア< int 、int > y ) {         
        abs ( x.first - y.first ) + abs ( x.second - y.second )を返します。​​​​​       
    };
    ( int b = 0 ; b < N ; ++ b )の場合{         
        for ( int c = 0 ; c < M ; ++ c ) { // 宅配便 -> ボトル -> レストラン           
            コスト[ b ][ c ] = 
                dist (宅配便業者[ c ],ボトル[ b ]) + dist (ボトル[ b ],残り);    
        }
        for ( int _ = 0 ; _ < N - 1 ; ++ _ ) { // レストラン -> ボトル -> レストラン             
            コスト[ b ][ _ + M ] = 2 * dist (ボトル[ b ]、残り);       
        }
    }
    cout << hungarian (コスト). back () << " \n " ;    
}

intメイン（）{  
    sanity_check_ハンガリー語();
    コルドンブルー();
}

ハンガリアンアルゴリズムは、最小コストフローの逐次最短経路アルゴリズムと同等であると見ることができます。 ^{[8] [9]では、}ジョンソンのアルゴリズムの再重み付け手法を使用して最短経路を見つけます。前のセクションの実装は、この関係を強調するように次のように書き直されています。ワーカーのポテンシャルが、定数オフセットまで前のソリューションのポテンシャルと等しいことを確認できます。グラフがまばらな場合（ジョブとワーカーのペアのみが許可されている）、フィボナッチヒープを使用して決定することで、すべてのワーカーを反復処理して最小距離のワーカーを見つける代わりに、このアルゴリズムを時間 内に実行するように最適化できます（ここで言及されています）。 ${\displaystyle h}$${\displaystyle 0\dots W-1}$${\displaystyle y}$${\displaystyle M}$${\displaystyle O(JM+J^{2}\log W)}$${\displaystyle w_{\text{next}}}$${\displaystyle W}$

テンプレート< class T > vector < T > hungarian ( const vector < vector < T >> & C ) {       
    定数int J = ( int ) size ( C )、W = ( int ) size ( C [ 0 ] )。       
    アサート( J <= W );  
    // job[w] = w番目のワーカーに割り当てられたジョブ、またはジョブが割り当てられていない場合は-1
    // 注: 便宜上、W 番目のワーカーが追加されました
    ベクトル< int >ジョブ( W + 1 , -1 );    
    ベクトル< T > h ( W ); // ジョンソンポテンシャル   
    ベクトル<T>の答え;​ 
    T ans_cur = 0 ;   
    const T inf = numeric_limits < T >:: max ();    
    // ポテンシャル付きダイクストラ法を使用して j_cur 番目のジョブを割り当てる
    ( int j_cur = 0 ; j_cur < J ; ++ j_cur ) {​         
        int w_cur = W ; // 最小距離の未訪問ワーカー     
        ジョブ[ w_cur ] = j_cur ;  
        vector < T > dist ( W + 1 , inf ); // ジョンソン縮約距離      
        分布[ W ] = 0 ;  
        vector < bool > vis ( W + 1 ); // すでに訪問したかどうか        
        vector < int > prv ( W + 1 , -1 ); // 最短経路上の前のワーカー      
        while ( job [ w_cur ] != -1 ) { // ダイクストラステップ: ヒープから最小ワーカーをポップする       
            T最小距離= inf ;   
            vis [ w_cur ] = true ;  
            int w_next = -1 ; // 最小距離を持つ次の未訪問ワーカー     
            // 最短経路を w_cur -> job[w_cur] -> w で拡張することを検討します
            ( int w = 0 ; w < W ; ++ w ) {​         
                if ( ! vis [ w ]) {  
                    // 削減されたエッジの重みの合計 w_cur -> job[w_cur] -> w
                    Tエッジ= C [ジョブ[ w_cur ]][ w ] - h [ w ];     
                    w_cur ! = Wの場合{    
                        エッジ-= C [ジョブ[ w_cur ]][ w_cur ] - h [ w_cur ];    
                        assert ( edge >= 0 ); // ジョンソンポテンシャルの結果    
                    }
                    ckmin ( dist [ w ], dist [ w_cur ] + edge )の場合、prv [ w ] = w_cur ;       
                    ckmin ( min_dist , dist [ w ])の場合、w_next = w ;     
                }
            }
            w_cur = w_next ;  
        }
        for ( int w = 0 ; w < W ; ++ w ) { // ポテンシャルを更新           
            ckmin (分布[ w ]、分布[ w_cur ] )。 
            h [ w ] +=距離[ w ];  
        }
        ans_cur += h [ w_cur ];  
        for ( int w ; w_cur != W ; w_cur = w )ジョブ[ w_cur ] =ジョブ[ w = prv [ w_cur ]];             
        回答.push_back ( ans_cur ) ;
    }
    回答を返す; 
}