詳細はC++ハンガリーアルゴリズムを実現します。
9459 ワード
一、ハンガリーのアルゴリズム紹介
ハンガリーのアルゴリズム（Hungarian algorithm）は主に二分図との整合に関する問題を解決するために使われていますので、まず二点図を調べてみます。
二分割図（Bipartite graph）は、2つの部分に分けられ、各部分の点が互いに接続されていない特殊な図である。下図は典型的な二分割図です。
上の二点図では、各辺の端点がそれぞれ点セットXとYの中にあることが見られます。ハンガリーのアルゴリズムは主に二つの問題を解決するために用いられます。二点図の最大整合数と最小点カバー数を求めます。
そう言えば抽象的すぎて、私たちは今実際の問題から出発します。
二、最大マッチング問題
上の話を読んで、読者は雲の中の霧の中のと感じることができることを信じます。これは何ですか？これは何の役に立つか？ですから、私たちはこの二点図を少し手足にして、次のようにします。
現在のボーイズとガールズはそれぞれ2つのポイント集で、中のポイントは男の子と女の子で、彼らの間に「曖昧関係」があると表しています。最大のマッチング問題は、もしあなたがお嬢さんであれば、曖昧な関係の男女ペアを取り持つことができますが、最大何組のカップルができますか？数学的表現：二分図の中で最大何本の公共の端がない辺を見つけることができますか？
ハンガリーのアルゴリズムはどのように動作しているか見てみましょう。
私たちはB 1から見て（男女平等、女子から見てもいいです）、彼とG 2は曖昧です。それではとりあえず彼をG 2に接続します。
B 2を見にきても、B 2もG 2が好きです。この時G 2はもう「名花の持ち主」になりました。私たちは逆にG 2が手配されている彼氏を見ます。B 1です。他の選択肢がありますか？あります。G 4、G 4はまだ手配されていません。B 1にG 4を手配します。
B 3、B 3に直接G 1をつければ大丈夫です。B 4に関してはG 4だけが好きで、G 4は現在B 1を配合しています。B 1はG 4以外にG 2を選ぶことができますが、B 1がG 2、G 2の原付B 2を選ぶと選択できなくなります。私たちは一回りしましたが、B 4は独身に運命付けられています。かわいそうです。今まで考えられたことがないG 3の方がもっとかわいそうです）
これはハンガリーのアルゴリズムの流れです。具体的な実現についてはコードを見てみます。
三、一番小さい点で問題をカバーする
もう一つの二分割図についての問題は一番小さい点をカバーすることです。私たちは一番少ない点を見つけたいです。二分割図のすべての辺に少なくとも一つの端点があるようにします。逆に言えば、これらの点を含む辺を削除して、すべての辺を削除することができます。
これはなぜハンガリーのアルゴリズムで解決できますか？長い間議論したいと思ったら間違いです。定理が必要です。
（Krong定理）
一つの二分割図の最大整合数はこの図の最小点カバー数に等しい。
はい、今回はもう終わります。私達は数学をやっているのではなく、証明は必要ありません。しかし、一番小さいカバーポイントセットを直観的に探す方法を提供します。左側の成功点から出発して、ハンガリーのアルゴリズムの流れ（即ち紫の矢印）を歩いて、左の未経過点と右側の通過点、すなわち一番小さい点カバーを構成します。すなわち、図中のB 3、G 2、G 4）
左の各ノードについては、拡張路を見つけるには、最大で2分割図を1回通過するので、このアルゴリズムの時間的複雑さはO（MN）である。
四、ハンガリーアルゴリズムの応用
いくつかの問題は、一見上の男女カップルの問題と似ているところがありません。実はハンガリーのアルゴリズムを使ってもいいです。たとえば:
4.1、（洛谷P 129）[ZJOI 2007]マトリックスゲーム
テーマの説明
Qさんはとても頭がいい子供です。チェスのほかに、コンピューターゲームDDマトリックスゲームも好きです。マトリックスゲームは一つの$Nにあります。× 白黒の方陣で行います。このマトリクスは毎回2つの動作が可能です。
行の交換操作：マトリックスの任意の2行を選択し、この2行を交換します。すなわち、対応する格子の色を交換します。
列交換操作：行列の任意の2列を選択し、この2列を交換します。すなわち、対応する格子の色を交換します。
ゲームの目標は、何回かの操作によって、正方形の主対角線（左上から右下までの連線）上の格子が黒になるようにします。
いくつかの関所については、小Qはそれを考えきれず、彼はこれらの関門が全く解けていないのではないかと疑い始めました。そこで小Qは、これらのレベルが解けているかどうかを判断するためのプログラムを書くことにしました。
入力フォーマット
最初の行は整数Tを含み、データのグループ数を表します。
次にTグループのデータを含み、各グループのデータの第1の挙動は整数Nであり、正方行列の大きさを表す。次にNは一つの$Nを行います。× N$の01行列（0は白、1は黒）です。
出力フォーマット
T行を含む。各グループのデータに対して、レベルが解けたら、行のYesを出力します。1行Noを出力します。
行列を二分割図に変換します。（左の集合は各行、右の集合は各列、ある位置は1の行とその列の間に境界があります。）X 1をY 1、X 2をY 2、…と一連の交換操作を行いたいです。
みんなは想像することができて、いわゆる交換、等価で名前を変えることができるのではありませんか？現在の二分図の構造が変わらないまま、右側の点の番号を変えられます。これは交換の効果と同じです。
X 1、X 2…Y 1、Y 2…と一対一で対応させたいですが、原図の最大マッチング数は4だけでいいです。これは組み合わせ数学における相異代表系の概念と一致する）。コードは以下の通りです
OIBHの組織の鼻息に直面して、コナンは牛小屋に深く入り込むことを決定して、虚実を探ってみます。
彼は熟慮の末、OIBH組織の正門から入ることにした。
OIBHのゲートには不思議なロックがあります。
ロックはM＊Nの格子からなり、中には格子の突起（灰色の格子）があります。操作するたびに、ある行またはある列の格子を押し続けます。
コナンが組織の限られた回数の内ですべての格子をすべて押し続けることができるならば、彼は本部に入ることができます。
コナンに指定された鍵を開くために必要な最低回数を計算してください。
読み込み/Input:
最初の行の2つは100を超えない正の整数Nで、Mは行列の長さと幅を表します。
以下のN行のM個の数が0でない、すなわち1が凸状の方眼である。
出力/アウトプット:
一つの整数が必要な最低回数
もし私たちがサンプルの行列を二分割図の形式に変換したら、このようになります。
行または列を押すと、ある点につながるすべての辺を削除します。今は一番少ない操作回数が必要です。考えてみてください。これは一番小さい点のカバー数を求めているのではないですか？だから直接にハンガリーのアルゴリズムをセットすればいいです。コード略
4.3、（TYVJ P 1035）ボードカバー
記述Description
n n(n==100)のチェスボードを提供します。中にはいくつかの点が削除されています。
入力フォーマットInput Format
第1の行為n，m（m個の削除がある格子を示す）
2行目からm＋1行目x，yは、それぞれ、格子を削除する位置を表します。
xはx行目
yは第y列とする
出力フォーマットOutput Format
1つの数、すなわち最大カバーの数です。
経典のドミノのカバー問題はみんなよく知っています。私達は碁盤を染色して、各ドミノのカルタがちょうど白い格子と黒い格子を覆っています。
いくつかの格子を削除しました。
今はドミノの最大カバー数が必要です。
私たちは染色したあと、黒と白の格子は二点図を構成できます。各白の格子は黒の格子だけと繋がっています。各黒の格子も白の格子だけと繋がっています。すべての黒と白の格子番号を与えた後、削除されていない各格子を上下左右に隣接した削除されていない格子に接続します。この二点図の最大マッチング数は、私たちが一番多くのドミノの数を置くことができることは明らかです。注意データ範囲が大きいので、隣接表で図を保存します。
ハンガリーのアルゴリズム（Hungarian algorithm）は主に二分図との整合に関する問題を解決するために使われていますので、まず二点図を調べてみます。
二分割図（Bipartite graph）は、2つの部分に分けられ、各部分の点が互いに接続されていない特殊な図である。下図は典型的な二分割図です。
上の二点図では、各辺の端点がそれぞれ点セットXとYの中にあることが見られます。ハンガリーのアルゴリズムは主に二つの問題を解決するために用いられます。二点図の最大整合数と最小点カバー数を求めます。
そう言えば抽象的すぎて、私たちは今実際の問題から出発します。
二、最大マッチング問題
上の話を読んで、読者は雲の中の霧の中のと感じることができることを信じます。これは何ですか？これは何の役に立つか？ですから、私たちはこの二点図を少し手足にして、次のようにします。
現在のボーイズとガールズはそれぞれ2つのポイント集で、中のポイントは男の子と女の子で、彼らの間に「曖昧関係」があると表しています。最大のマッチング問題は、もしあなたがお嬢さんであれば、曖昧な関係の男女ペアを取り持つことができますが、最大何組のカップルができますか？数学的表現：二分図の中で最大何本の公共の端がない辺を見つけることができますか？
ハンガリーのアルゴリズムはどのように動作しているか見てみましょう。
私たちはB 1から見て（男女平等、女子から見てもいいです）、彼とG 2は曖昧です。それではとりあえず彼をG 2に接続します。
B 2を見にきても、B 2もG 2が好きです。この時G 2はもう「名花の持ち主」になりました。私たちは逆にG 2が手配されている彼氏を見ます。B 1です。他の選択肢がありますか？あります。G 4、G 4はまだ手配されていません。B 1にG 4を手配します。
B 3、B 3に直接G 1をつければ大丈夫です。B 4に関してはG 4だけが好きで、G 4は現在B 1を配合しています。B 1はG 4以外にG 2を選ぶことができますが、B 1がG 2、G 2の原付B 2を選ぶと選択できなくなります。私たちは一回りしましたが、B 4は独身に運命付けられています。かわいそうです。今まで考えられたことがないG 3の方がもっとかわいそうです）
これはハンガリーのアルゴリズムの流れです。具体的な実現についてはコードを見てみます。
int M, N; //M, N 、
int Map[MAXM][MAXN]; //
int p[MAXN]; //
bool vis[MAXN]; //
bool match(int i)
{
for (int j = 1; j <= N; ++j)
if (Map[i][j] && !vis[j]) //
{
vis[j] = true; //
if (p[j] == 0 || match(p[j])) // ，
{
p[j] = i; //
return true; //
}
}
return false; // ， ，
}
int Hungarian()
{
int cnt = 0;
for (int i = 1; i <= M; ++i)
{
memset(vis, 0, sizeof(vis)); // vis
if (match(i))
cnt++;
}
return cnt;
}三、一番小さい点で問題をカバーする
もう一つの二分割図についての問題は一番小さい点をカバーすることです。私たちは一番少ない点を見つけたいです。二分割図のすべての辺に少なくとも一つの端点があるようにします。逆に言えば、これらの点を含む辺を削除して、すべての辺を削除することができます。
これはなぜハンガリーのアルゴリズムで解決できますか？長い間議論したいと思ったら間違いです。定理が必要です。
（Krong定理）
一つの二分割図の最大整合数はこの図の最小点カバー数に等しい。
はい、今回はもう終わります。私達は数学をやっているのではなく、証明は必要ありません。しかし、一番小さいカバーポイントセットを直観的に探す方法を提供します。左側の成功点から出発して、ハンガリーのアルゴリズムの流れ（即ち紫の矢印）を歩いて、左の未経過点と右側の通過点、すなわち一番小さい点カバーを構成します。すなわち、図中のB 3、G 2、G 4）
左の各ノードについては、拡張路を見つけるには、最大で2分割図を1回通過するので、このアルゴリズムの時間的複雑さはO（MN）である。
四、ハンガリーアルゴリズムの応用
いくつかの問題は、一見上の男女カップルの問題と似ているところがありません。実はハンガリーのアルゴリズムを使ってもいいです。たとえば:
4.1、（洛谷P 129）[ZJOI 2007]マトリックスゲーム
テーマの説明
Qさんはとても頭がいい子供です。チェスのほかに、コンピューターゲームDDマトリックスゲームも好きです。マトリックスゲームは一つの$Nにあります。× 白黒の方陣で行います。このマトリクスは毎回2つの動作が可能です。
行の交換操作：マトリックスの任意の2行を選択し、この2行を交換します。すなわち、対応する格子の色を交換します。
列交換操作：行列の任意の2列を選択し、この2列を交換します。すなわち、対応する格子の色を交換します。
ゲームの目標は、何回かの操作によって、正方形の主対角線（左上から右下までの連線）上の格子が黒になるようにします。
いくつかの関所については、小Qはそれを考えきれず、彼はこれらの関門が全く解けていないのではないかと疑い始めました。そこで小Qは、これらのレベルが解けているかどうかを判断するためのプログラムを書くことにしました。
入力フォーマット
最初の行は整数Tを含み、データのグループ数を表します。
次にTグループのデータを含み、各グループのデータの第1の挙動は整数Nであり、正方行列の大きさを表す。次にNは一つの$Nを行います。× N$の01行列（0は白、1は黒）です。
出力フォーマット
T行を含む。各グループのデータに対して、レベルが解けたら、行のYesを出力します。1行Noを出力します。
行列を二分割図に変換します。（左の集合は各行、右の集合は各列、ある位置は1の行とその列の間に境界があります。）X 1をY 1、X 2をY 2、…と一連の交換操作を行いたいです。
みんなは想像することができて、いわゆる交換、等価で名前を変えることができるのではありませんか？現在の二分図の構造が変わらないまま、右側の点の番号を変えられます。これは交換の効果と同じです。
X 1、X 2…Y 1、Y 2…と一対一で対応させたいですが、原図の最大マッチング数は4だけでいいです。これは組み合わせ数学における相異代表系の概念と一致する）。コードは以下の通りです
#include <cstdio>
#include <cstring>
int Map[205][205], p[205], vis[205], N, T;
bool match(int i){
for (int j = 1; j <= N; ++j){
if (Map[i][j] && !vis[j]){
vis[j] = 1;
if (p[j] == 0 || match(p[j])){
p[j] = i;
return true;
}
}
}
return false;
}
int Hungarian(){
int cnt = 0;
for (int i = 1; i <= N; ++i){
memset(vis, 0, sizeof(vis));
if (match(i))
cnt++;
}
return cnt;
}
int main(){
scanf("%d", &T);
while (T--){
scanf("%d", &N);
memset(p, 0, sizeof(p));
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
scanf("%d", &Map[i][j]);
puts(Hungarian() == N ? "Yes" : "No");
}
return 0;
}OIBHの組織の鼻息に直面して、コナンは牛小屋に深く入り込むことを決定して、虚実を探ってみます。
彼は熟慮の末、OIBH組織の正門から入ることにした。
OIBHのゲートには不思議なロックがあります。
ロックはM＊Nの格子からなり、中には格子の突起（灰色の格子）があります。操作するたびに、ある行またはある列の格子を押し続けます。
コナンが組織の限られた回数の内ですべての格子をすべて押し続けることができるならば、彼は本部に入ることができます。
コナンに指定された鍵を開くために必要な最低回数を計算してください。
読み込み/Input:
最初の行の2つは100を超えない正の整数Nで、Mは行列の長さと幅を表します。
以下のN行のM個の数が0でない、すなわち1が凸状の方眼である。
出力/アウトプット:
一つの整数が必要な最低回数
もし私たちがサンプルの行列を二分割図の形式に変換したら、このようになります。
行または列を押すと、ある点につながるすべての辺を削除します。今は一番少ない操作回数が必要です。考えてみてください。これは一番小さい点のカバー数を求めているのではないですか？だから直接にハンガリーのアルゴリズムをセットすればいいです。コード略
4.3、（TYVJ P 1035）ボードカバー
記述Description
n n(n==100)のチェスボードを提供します。中にはいくつかの点が削除されています。
入力フォーマットInput Format
第1の行為n，m（m個の削除がある格子を示す）
2行目からm＋1行目x，yは、それぞれ、格子を削除する位置を表します。
xはx行目
yは第y列とする
出力フォーマットOutput Format
1つの数、すなわち最大カバーの数です。
経典のドミノのカバー問題はみんなよく知っています。私達は碁盤を染色して、各ドミノのカルタがちょうど白い格子と黒い格子を覆っています。
いくつかの格子を削除しました。
今はドミノの最大カバー数が必要です。
私たちは染色したあと、黒と白の格子は二点図を構成できます。各白の格子は黒の格子だけと繋がっています。各黒の格子も白の格子だけと繋がっています。すべての黒と白の格子番号を与えた後、削除されていない各格子を上下左右に隣接した削除されていない格子に接続します。この二点図の最大マッチング数は、私たちが一番多くのドミノの数を置くことができることは明らかです。注意データ範囲が大きいので、隣接表で図を保存します。
#include <cstdio>
#include <cstring>
#define MAXN 5500
struct Edges
{
int to, next;
} edges[MAXN * 8];
int Map[105][105], head[MAXN], p[MAXN], vis[MAXN], N, cnt_edge;
inline int add(int from, int to)
{
edges[++cnt_edge].next = head[from];
head[from] = cnt_edge;
edges[cnt_edge].to = to;
}
inline int trans(int i, int j, int n) //
{
return ((i - 1) * n + j + 1) / 2;
}
bool match(int i)
{
for (int e = head[i]; e; e = edges[e].next)
{
int j = edges[e].to;
if (!vis[j])
{
vis[j] = true;
if (p[j] == 0 || match(p[j]))
{
p[j] = i;
return true;
}
}
}
return false;
}
int Hungarian()
{
int cnt = 0;
for (int i = 1; i <= N; ++i)
{
memset(vis, 0, sizeof(vis));
if (match(i))
cnt++;
}
return cnt;
}
int main()
{
int n, m, x, y;
scanf("%d%d", &n, &m);
N = (n * n + 1) / 2;
memset(Map, -1, sizeof(Map));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
Map[i][j] = 0;
for (int i = 0; i < m; ++i)
{
scanf("%d%d", &x, &y);
Map[x][y] = -1;
}
for (int i = 1; i <= n; i++)
for (int j = i % 2 ? 1 : 2; j <= n; j += 2)
if (Map[i][j] == 0)
{
if (Map[i + 1][j] != -1)
add(trans(i, j, n), trans(i + 1, j, n));
if (Map[i][j + 1] != -1)
add(trans(i, j, n), trans(i, j + 1, n));
if (Map[i - 1][j] != -1)
add(trans(i, j, n), trans(i - 1, j, n));
if (Map[i][j - 1] != -1)
add(trans(i, j, n), trans(i, j - 1, n));
}
printf("%d
", Hungarian());
return 0;
}