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

参考博客：链式前向星 -- 最通俗易懂的讲解、算法讲解：二分图匹配【图论】、趣写算法系列之 -- 匈牙利算法、匈牙利算法与增广路径

暑假整的忘了发 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 对学生互相认识。将学生分成两组，以便同一组中的任何两个学生都不认识。如果可以实现此目标，则将他们安排在双人间。请记住，只有出现在先前给定集合中的巴黎才能住在同一房间，这意味着只有已知的学生才能住在同一房间。计算可安排到这些双人间中的最大对数。
思路：
二分图判断和匹配，二分图的判断采用染色法，匹配采用匈牙利算法