参考ブログ：チェーン式前向星 -- 最もわかりやすい説明、アルゴリズム解説：二部グラフマッチング【グラフ理論】、面白いアルゴリズムシリーズ -- ハンガリアンアルゴリズム、ハンガリアンアルゴリズムと増加経路
夏休みの間に忘れてしまった 2333
@TOC
一、チェーン式前向星#
1. とは#
隣接リストが書きにくいが効率が良いとし、隣接行列が書きやすいが効率が悪いとするなら、前向星は比較的中庸なデータ構造です。前向星は確かに良いですが、効率は高くありません。そして、チェーン式前向星に最適化されると、効率も大幅に向上しました。世界中でチェーン式前向星の使用はそれほど広くはありませんが、複雑な隣接リストを書くことを避けたい場合、チェーン式前向星も非常に優れたデータ構造です。
——百度百科より引用
チェーン式前向星は実際には静的に構築された隣接リストであり、特別な辺集合配列で、その時間効率は O（m）、空間効率も O（m）です。遍歴効率も O（m）であり、すべてのノードの隣接辺を簡単に見つけることができます。
2. グラフの保存方法#
以下の配列の意味が必要です：
- head [i] 配列は、i を起点とする最初の辺の番号を示し、一般的に - 1 で初期化され、この辺を起点とする辺がないことを示します。
- edge [i] 構造配列では、edge [i].to は i 番目の辺の終点を示し、edge [i].Next は i 番目の辺と同じ起点の次の辺の保存位置を示し、edge [i].w は辺の重みを示します。
定義と初期化#
const int maxn = 10000;//最大頂点数
int N,M,mcnt;//頂点数、辺数
int head[maxn];//iを起点とする最初の辺がedge配列のインデックス
struct Edge {
int to, w, Next;//終点、辺の重み、同じ起点の次の辺の番号
} edge[maxn];
void init() {
memset(head, -1, sizeof(head));
mcnt = 0;
}
辺の追加#
void add_edge(int u, int v, int w) {
edge[mcnt].to = v;
edge[mcnt].w = w;
edge[mcnt].Next = head[u];//次の辺の番号をNextに割り当て
head[u] = mcnt++;//head配列を更新
}
遍歴#
for(int i = 1; i <= N; ++i) {
for(int j = head[i]; j != -1; j = edge[j].Next) { //iを起点とする辺を遍歴
//他の操作
}
}
二、二部グラフマッチング#
1. 二部グラフ#
百度百科の説明は以下の通りです：
二部グラフは二部図とも呼ばれ、グラフ理論における特別なモデルです。 G=(V,E) が無向グラフであり、頂点 V が互いに交差しない 2 つの部分集合 (A,B) に分割でき、グラフ内の各辺（i，j）がこの 2 つの異なる頂点集合 (i in A,j in B) に属する場合、グラフ G は二部グラフと呼ばれます。
簡単に言えば、グラフが 2 つの部分に分かれ、異なる部分間の点にのみ辺が存在し、同じ部分間の点には辺が存在しないということです。
2. マッチング#
- 二部グラフ G が与えられ、G の部分グラフ M において、M の辺集合 {E} の任意の 2 つの辺は同じ頂点に依存しない場合、M はマッチングと呼ばれます。
- 極大マッチング (Maximal Matching) とは、現在完了しているマッチングの下で、未完了のマッチングの辺を追加することによってマッチングの辺の数を増やすことができないことを指します。
- 最大マッチング (maximum matching) とは、すべての極大マッチングの中で辺の数が最も多いマッチングです。このような辺の数が最大の部分集合をグラフの最大マッチング問題と呼びます。
- マッチングの中で、グラフ内のすべての頂点がグラフ内のある辺に関連付けられている場合、このマッチングは完全マッチングと呼ばれ、完備マッチングとも呼ばれます。
- P がグラフ G の中で 2 つの未マッチ頂点を連結する経路であり、M に属する辺と M に属さない辺が P 上で交互に現れる場合、P は M に対する増加経路と呼ばれます。
3. ハンガリアンアルゴリズム#
ハンガリアンアルゴリズムは、二部グラフの多重マッチングを除いて、二部グラフマッチングの中で使用できます。ほぼ二部グラフマッチングの核心アルゴリズムであり、二部グラフの多重マッチングを除いて使用でき、実際にはネットワークフローの考え方であり、その核心は増加経路を探すことです。具体的な操作は、うーん。。ラブマッチングです。
具体的な考え方はこのブログを参照してください面白いアルゴリズムシリーズ -- ハンガリアンアルゴリズム
ここにまとめを置いておきます：機会があれば、機会を創造することも必要です
コアコード#
妹を探す再帰【ではない】
bool find(int x){
int i,j;
for (j=1;j<=m;j++){ //各妹をスキャン
if (line[x][j]==true && used[j]==false)
//もし曖昧でまだマークされていない場合（ここでのマークは、この検索でその妹の帰属問題を変更しようとしたが、成功しなかったことを意味し、無駄な労力を使う必要はありません）
{
used[j]=1;
if (girl[j]==-1 || find(girl[j])) {
//名花無主または空きができる場合、ここで再帰を使用
girl[j]=x;
return true;
}
}
}
return false;
}
主プログラムで各男をスキャンし、used をリセットする操作に注意
for (i=1;i<=n;i++)
{
memset(used,0,sizeof(used)); //このステップでリセット
if find(i) all+=1;
}
いくつかの例題#
A - Fire Net#
問題の概要と考え方#
概要：
N*N の都市地図で、「.” は 4 方向に射撃できる小型城塞を設置できることを示し、「X」は射撃を遮る壁があることを示します。都市内にできるだけ多くの小型城塞を設置し、2 つの小型城塞が互いに破壊できないようにします。小型城塞の配置は合法であり、地図上に同じ水平行または垂直列に 2 つの小型城塞がない場合に限り、少なくとも 1 つの壁がそれらを隔てている必要があります。
考え方：
各行を最初に遍歴し、間に壁がある場合は異なる列と見なします。これを二部グラフの X 領域とし、各列を遍歴し、間に壁がある場合は異なる行と見なします。これを Y 領域とし、edge [i][j] は X 領域の点 i と Y 領域の点 j の間に辺があるかどうかを示し、この二部グラフの最大マッチングを求めます（小型城塞は行列の交点に配置され、交点は一意です）。この問題は明らかに隣接行列を使用して変換されたグラフを保存する方が便利で迅速です…
コード#
ここで col 配列は - 1 で初期化する必要があります
// A - Fire Net
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 1005;
const int inf = 0x3f3f3f;
int N,M,rcnt,ccnt,ans;
string str;
struct Vertex {
char flag;
int r, c;//この点が位置する実際の行列
}map[maxn][maxn],now;
int edge[maxn][maxn];
int col[maxn];
bool used[maxn];
void init() {
rcnt = ccnt = ans = 0;
memset(used, 0, sizeof(used));
memset(col, -1, sizeof(col));
memset(edge, 0, sizeof(edge));
}
bool find_x(int x) {
for(int j = 0; j < ccnt; ++j) {
if(edge[x][j] == 1 && !used[j]) {
used[j] = true;
if(col[j] == -1 || find_x(col[j])) {
col[j] = x;
return true;
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
while(cin >> N && N) {
init();
for(int i = 0; i < N; ++i) {
cin >> str;
for(int j = 0; j < N; ++j) {
map[i][j].flag = str[j];
}
}
for(int j = 0; j < N; ++j, ++ccnt) {//各列
for(int i = 0; i < N; ++i) {
if(map[i][j].flag == 'X' && i+1 < N && map[i+1][j].flag != 'X')
++ccnt;//各列の中で非連結なものは異なる列と見なす
map[i][j].c = ccnt;
}
}
for(int i = 0; i < N; ++i, ++rcnt) {//各行
for(int j = 0; j < N; ++j) {
if(map[i][j].flag == 'X' && j+1 < N && map[i][j+1].flag != 'X')
++rcnt;//各行の中で非連結なものは異なる行と見なす
map[i][j].r = rcnt;
}
}
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
if(map[i][j].flag == '.') {
now = map[i][j];
edge[now.r][now.c] = 1;
}
}
}
for(int i = 0; i < rcnt; ++i) {
memset(used, 0, sizeof(used));
if(find_x(i)) ans++;
}
cout << ans << endl;
}
return 0;
}
B - 学生の宿泊#
問題の概要と考え方#
概要：
n 人の学生が与えられ、m 組の学生が互いに知り合いであることを伝えます。同じグループ内の任意の 2 人の学生が互いに知り合いでないように、学生を 2 つのグループに分けます。この目標を達成できる場合、彼らを二人部屋に配置します。以前に与えられたペアにのみ同じ部屋に住むことができることを忘れないでください。これらの二人部屋に配置できる最大のペア数を計算します。
考え方：
二部グラフの判定とマッチング、二部グラフの判定には染色法を使用し、マッチングにはハンガリアンアルゴリズムを使用します。