鏈式前向星存圖、二分圖匹配之匈牙利算法模板&分析（存用）

參考博客：鏈式前向星 -- 最通俗易懂的講解、算法講解：二分圖匹配【圖論】、趣寫算法系列之 -- 匈牙利算法、匈牙利算法與增廣路徑

暑假整的忘了發 2333

一、鏈式前向星#

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 可分割为两个互不相交的子集 (A,B)，并且图中的每条边（i，j）所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集 (i in A,j in B)，则称图 G 为一个二分图。

簡單來說，就是一個圖被分兩部分，只有不同部分之間的點存在邊，相同部分之間的點是不存在邊的

在這裡插入圖片描述

2. 匹配#

給定一個二分圖 G，在 G 的一個子圖 M 中，M 的邊集 {E} 中的任意兩條邊都不依附於同一個頂點，則稱 M 是一个匹配。
極大匹配 (Maximal Matching) 是指在當前已完成的匹配下，無法再通過增加未完成匹配的邊的方式來增加匹配的邊數。
最大匹配 (maximum matching) 是所有極大匹配當中邊數最大的一个匹配。選擇這樣的邊數最大的子集稱為圖的最大匹配問題。
如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯，則稱此匹配為完全匹配，也稱作完備匹配。
若 P 是圖 G 中一條聯通兩個未匹配頂點的路徑，且屬於 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 的城市地圖，“.” 代表可以放置一個小型城堡向四個方向射擊，“X” 代表有牆可以擋住射擊，在一個城市中放置儘可能多的小型城堡，以使沒有兩個小型城堡能夠相互摧毀。小型城堡的配置是合法的，當且僅當地圖上沒有兩個小型城堡位於同一水平行或垂直列上，除非至少有一堵牆將它們隔開
思路：
先遍歷每行，中間有牆的算不同列，作為二分圖中的 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 - The Accomodation of Students #

題目大意及思路#

大意：
給出 n 個學生，告訴你 m 對學生互相認識。將學生分成兩組，以便同一組中的任何兩個學生都不認識。如果可以實現此目標，則將他們安排在雙人間。請記住，只有出現在先前給定集合中的巴黎才能住在同一房間，這意味著只有已知的學生才能住在同一房間。計算可安排到這些雙人間中的最大對數。
思路：
二分圖判斷和匹配，二分圖的判斷採用染色法，匹配採用匈牙利算法