banner
cos

cos

愿热情永存,愿热爱不灭,愿生活无憾
github
tg_channel
bilibili

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

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

暑假整的忘了发 2333


@TOC


一、链式前向星#

1. 是什么#

如果说邻接表是不好写但效率好,邻接矩阵是好写但效率低的话,前向星就是一个相对中庸的数据结构。前向星固然好些,但效率并不高。而在优化为链式前向星后,效率也得到了较大的提升。虽然说,世界上对链式前向星的使用并不是很广泛,但在不愿意写复杂的邻接表的情况下,链式前向星也是一个很优秀的数据结构。

——摘自百度百科

链式前向星其实就是静态建立的邻接表,一种特殊边集数组,其时间效率为 O(m),空间效率也为 O(m)。遍历效率也为 O(m),它能很方便的找出所有结点的邻接边

2. 如何存图#

我们需要以下数组的含义:

  1. head [i] 数组,表示以 i 为起点的第一条边的编号,一般初始化为 - 1,说明没有以这个边为起点的边了。
  2. 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 对学生互相认识。将学生分成两组,以便同一组中的任何两个学生都不认识。如果可以实现此目标,则将他们安排在双人间。请记住,只有出现在先前给定集合中的巴黎才能住在同一房间,这意味着只有已知的学生才能住在同一房间。计算可安排到这些双人间中的最大对数。
思路:
  二分图判断和匹配,二分图的判断采用染色法,匹配采用匈牙利算法

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。