首页 > 其他分享 >二分图备忘录

二分图备忘录

时间：2023-10-16 21:01:42浏览次数：42  
标签：二分 匹配 get int 备忘录 && ct

本文是写给作者自己看的

概念

指一张无向图G中，N个节点可以划分为两个集合A,B

集合A和B内部没有连边，A和B可以有连边（可以有空集）

Q：为什么不用三分图：
A：很简单，三分图分类更多，更麻烦。没有顺序关系有三种情况，有顺序关系则是六种（就像线段树不用三叉）

一些叫法

A集合内的点：左部点
B集合内的点：右部点

判定

充要条件：没有奇环

经典中的经典，显然要形成环，肯定是一个左部点，一个右部点......所以肯定是偶环。

具体实现：黑白染色，如果有相邻的点同色就不是二分图。

注意：图不一定连通！图不一定连通！图不一定连通！

模版：P1525 关押罪犯
其实可能用并查集的做法可能更广为人知，但是二分图更加直观。

你考虑这样一件事，就是说：可以二分一个阙值i，判断如果让影响力为i是否可行。那么就是让所有影响力大于i的罪犯二元组在不同的监狱里，显然，二分图匹配。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> v[20001];
struct stu{
	int from,to,val;
}jail[100001];
int maxn=0;
int col[20001];

bool dfs(int now,int c){
	col[now]=c;
	for(int i=0;i<v[now].size();i++){
		if(col[v[now][i]]){
			if(col[v[now][i]]==col[now]) return false;//相邻节点相同颜色
		}
		else{
			if(!dfs(v[now][i],3-c)) return false;//递归下去任何一条路径不满足要求都返回false,和后面的最大匹配很容易混淆
		}
	}
	return true;
}

bool check(int now){
	for(int i=1;i<=n;i++) v[i].clear(),col[i]=0;
	for(int i=1;i<=m;i++){
		if(jail[i].val>now){//所有影响力大于阙值的二元组
			v[jail[i].from].push_back(jail[i].to);
			v[jail[i].to].push_back(jail[i].from);
		}
	}
	for(int i=1;i<=n;i++){
		if(!col[i]){
			if(!dfs(i,1)) return false;//图不一定连通！
		}
	}
	return true;
}

int erfen(int l,int r){//交给二分
	if(l==r) return l;
	else if(l==r-1){
		if(check(l)) return l;
		else return r;
	}
	else{
		int mid=(l+r)/2;
		if(check(mid)) return erfen(l,mid);
		else return erfen(mid+1,r);
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>jail[i].from>>jail[i].to>>jail[i].val;
		maxn=max(maxn,jail[i].val);
	}
	cout<<erfen(0,maxn);
	return 0;
}

还可以练一练这个,思路不难：
CF85E Guard Towers

最大匹配

在一张二分图中选最多的不共点的边，边数就是最大匹配

怎么说呢，这东西网络流当然可以做。理论上来说，二分图的题目用网络流做都是有正确性的。

很多要输出方案并且数据范围比较小的时候基本实锤网络流。

匈牙利算法

广为人知的最大匹配算法

具体流程：
二分图的左部点向右部点连边。

枚举尚未匹配的左部点x，从x出发找增广路径到未匹配右部点y。注意，千万注意和前面的判定搞混了，最大匹配只要找到一条增广路径就可以。

二分图的最小点覆盖

在原图中选一个最小点集S,使得每一条边都至少有一个端点在S中。
(用最少的点覆盖所有的边)

和2-SAT区分，不是必须二选一，也可以二选二

konig 定理

o上面有两个点的，打不出来
二分图的最小点覆盖=二分图的最大匹配

证明：

首先，对于最大匹配中的每一条边，选一个点出来一定可以覆盖所有的边，由此可得二分图的最大匹配>=二分图的最小点覆盖

然后，让最小点覆盖点集里的每个点向外连一条边，可以覆盖所有的边。如果没有共点的边，数量等于最大匹配。如果有共点的，大于最小点覆盖，所以二分图的最大匹配<=二分图的最小点覆盖

综上，二分图的最小点覆盖=二分图的最大匹配

二分图的最小边覆盖

在原图中选一个最小边集S,使得每一点都为S中至少一条边的端点

二分图中最小边覆盖=顶点数-二分图最大匹配

二分图中最小边覆盖+最小顶点覆盖=顶点数。

最大独立集

在无向图中选取最大的点集S，S内任意2点之间都没有连边

二分图的最大独立集=总点数-最小点覆盖=总点数-最大匹配

证明：

显然把在最小点覆盖点集里的所有点删了以后剩余的点都不联通。于是二分图的最大独立集=总点数-最小点覆盖。

而前面证明了最小点覆盖=最大匹配

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n,r,c;
int tol;
vector<int> v[40001];
int match[40001];
bool vis[40001];
string s[210];
int ans;
bool ct[210][210];

bool hungray(int now){
	for(int i=0;i<v[now].size();i++){
		int to=v[now][i];
		if(!vis[to]){
			vis[to]=true;
			if(!match[to] || hungray(match[to])){
				match[to]=now;
				return true;
			}
		}
	}
	return false;
}

int get(int xx,int yy){
	return (xx-1)*n+yy;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	r=1,c=2;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		ct[a][b]=true;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!ct[i][j]){
				tol++;
				if(i+r<=n && j+c<=n && !ct[i+r][j+c]) v[get(i,j)].push_back(get(i+r,j+c));
				if(i+c<=n && j+r<=n && !ct[i+c][j+r]) v[get(i,j)].push_back(get(i+c,j+r));
				if(i+r<=n && j-c>=1 && !ct[i+r][j-c]) v[get(i,j)].push_back(get(i+r,j-c));
				if(i+c<=n && j-r>=1 && !ct[i+c][j-r]) v[get(i,j)].push_back(get(i+c,j-r));
				if(i-r>=1 && j+c<=n && !ct[i-r][j+c]) v[get(i,j)].push_back(get(i-r,j+c));
				if(i-c>=1 && j+r<=n && !ct[i-c][j+r]) v[get(i,j)].push_back(get(i-c,j+r));
				if(i-r>=1 && j-c>=1 && !ct[i-r][j-c]) v[get(i,j)].push_back(get(i-r,j-c));
				if(i-c>=1 && j-r>=1 && !ct[i-c][j-r]) v[get(i,j)].push_back(get(i-c,j-r));
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if((i+j)%2==0 && !ct[i][j]){
				memset(vis,0,sizeof(vis));
				if(hungray(get(i,j))) ans++;
			}
		}
	}
	//cout<<tol<<endl;
	cout<<tol-ans;
	return 0;
}

模版：
P3355 骑士共存问题

把方格黑白染色。显然在黑色格子上的马只能攻击在白色格子上的点，反之亦然，显然是二分图。

有一个细节。匈牙利求最大匹配肯定是跑不满的，但是先连右下角更容易匹配上，常数小很多。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,n,r,c;
int tol;
vector<int> v[40001];
int match[40001];
bool vis[40001];
string s[210];
int ans;
bool ct[210][210];

bool hungray(int now){
	for(int i=0;i<v[now].size();i++){
		int to=v[now][i];
		if(!vis[to]){
			vis[to]=true;
			if(!match[to] || hungray(match[to])){
				match[to]=now;
				return true;
			}
		}
	}
	return false;
}

int get(int xx,int yy){
	return (xx-1)*n+yy;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	r=1,c=2;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		ct[a][b]=true;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!ct[i][j]){
				tol++;
				if(i+r<=n && j+c<=n && !ct[i+r][j+c]) v[get(i,j)].push_back(get(i+r,j+c));
				if(i+c<=n && j+r<=n && !ct[i+c][j+r]) v[get(i,j)].push_back(get(i+c,j+r));
				if(i+r<=n && j-c>=1 && !ct[i+r][j-c]) v[get(i,j)].push_back(get(i+r,j-c));
				if(i+c<=n && j-r>=1 && !ct[i+c][j-r]) v[get(i,j)].push_back(get(i+c,j-r));
				if(i-r>=1 && j+c<=n && !ct[i-r][j+c]) v[get(i,j)].push_back(get(i-r,j+c));
				if(i-c>=1 && j+r<=n && !ct[i-c][j+r]) v[get(i,j)].push_back(get(i-c,j+r));
				if(i-r>=1 && j-c>=1 && !ct[i-r][j-c]) v[get(i,j)].push_back(get(i-r,j-c));
				if(i-c>=1 && j-r>=1 && !ct[i-c][j-r]) v[get(i,j)].push_back(get(i-c,j-r));
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if((i+j)%2==0 && !ct[i][j]){
				memset(vis,0,sizeof(vis));
				if(hungray(get(i,j))) ans++;
			}
		}
	}
	//cout<<tol<<endl;
	cout<<tol-ans;
	return 0;
}

最大团

在无向图G中选取最大的点集S，S内任意两点之间都有直接连边

在一般图中，这是一个NP问题，但是在补图为二分图的时候就不一样了。

首先说一下补图的概念

补图

在无向图G中，原来连边的点不连边，得到补图G次

于是有一个显然的结论：原图的最大团等于补图的最大独立集

有向图最小路径点覆盖

在一张有向无环图DAG中，用最少的不相交的路径覆盖所有的点。

实现方法：

  • 1.将原图中每一个点x拆为出点out[x]和入点in[x]

  • 2.对于原图中一条x->y的有向边，在新图中连边out[x],in[y]

显然这是一张二分图

  • 3.最小路径点覆盖=原图中的点数N-新图的最大匹配

证明：

首先可以认为有N条路径，我们要将它们合并。你考虑匹配的现实意义其实就是把两条路径首尾相接。也就是每匹配一次就少了一条路径。

也可以这么证明：

首先一条路径肯定是一条链。

那么一条路径只有1个入度为0的点和一个出度为0的点。所以路径最少等价于出度为0的点最少。如果出边被匹配一次出度为0的点就会减少一个

模版：
poj-2594 Treasure Exploration

#include<iostream>
#include<vector>
#define int long long
using namespace std;
int n,m;
vector<int> v[560];
int match[560];
bool dis[560][560];
bool vis[560];
int ans;

void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dis[i][k] && dis[k][j]) dis[i][j]=true;
			}
		}
	}
}

bool hungray(int now){
	for(int i=0;i<v[now].size();i++){
		int to=v[now][i];
		if(!vis[to]){
			vis[to]=true;
			if(!match[to] || hungray(match[to])){
				match[to]=now;
				return true;
			}
		}
	}
	return false;
}

signed main(){
	while(cin>>n>>m){
		ans=0;
		if(!n && !m) break;
		for(int i=1;i<=n;i++) v[i].clear(),match[i]=false;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dis[i][j]=false;
			}
		}
		for(int i=1;i<=m;i++){
			int a,b;
			cin>>a>>b;
			dis[a][b]=true;
		}
		floyd();//传递闭包 
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dis[i][j]) v[i].push_back(j);
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) vis[j]=false;
			if(hungray(i)) ans++;
		}
		cout<<n-ans<<endl;
	}
	return 0; 
}

输出方案模版：

P2764 最小路径覆盖问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
vector<int> v[160];
int match[160];
int help[160];
bool vis[160];
int ans;

bool hungray(int now){
	for(int i=0;i<v[now].size();i++){
		int to=v[now][i];
		if(!vis[to]){
			vis[to]=true;
			if(!match[to] || hungray(match[to])){
				match[to]=now;
				help[now]=to;
				return true;
			}
		}
	}
	return false;
}

void out_put(int now){
	while(help[now] && !vis[help[now]]){
		vis[now]=true;
		cout<<now<<" ";
		now=help[now];
	}
	if(!vis[now]){
		vis[now]=true;
		cout<<now;
	}
	cout<<endl;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) vis[j]=false;
		if(hungray(i)) ans++;
	}
	for(int i=1;i<=n;i++) vis[i]=false;
	for(int i=1;i<=n;i++){
		if(!match[i]) out_put(i);
	}
	cout<<n-ans;
	return 0; 
}

有向图最小可相交路径点覆盖

核心思想：转化为不相交的情况。将两点之间的间接到达转化为直接到达。

对，floyd求传递闭包，然后直接按不相交的方法跑

综合例题

eg1

P1129 [ZJOI2007] 矩阵游戏

一道很好的思维题。

假设有\(2* n\)个点分列两边，左部点i向右部点j连边表示(i,j)为1

此时最终的目标是有(1,1),(2,2),(3,3)...(n,n)这些边

考虑行交换和列交换的意义。

假设现在有(1,2),(2,1)，显然可以通过行列交换变成(1,1),(2,2)这两条边。画一个图，形象的理解就是把缠在一起的两条边绕开了，所以n条边缠在一起肯定可以把其变为目标状态。（当然，不能有(x,y),(z,y)这种情况出现）

所以，若最大匹配数为n则有解，反之无解。

AC记录

eg2

P2526 [SHOI2001] 小狗散步
这道题比较典，看到这句话：“Pandog 每次与主人相遇之前最多只去一个景点”很容易想到匹配，然后是这句话：“使它能够游览最多的景点”，这相当于告诉我们一个景点只去一次。所以直接能赶回来就连边。

AC记录

eg3

P2055 [ZJOI2009] 假期的宿舍

这题POJ-2594 Treasure Exploration

标签：二分,匹配,get,int,备忘录,&&,ct
From： https://www.cnblogs.com/wangwenhan/p/17758308.html

相关文章

  • 折半(二分)查找算法—高效搜索算法
    折半查找算法（BinarySearchAlgorithm）是一种高效的搜索算法，常用于已排序的数组或列表中进行查找操作。它的核心思想是通过比较中间元素与目标值的大小关系来确定目标值在数组的哪一部分，从而缩小搜索范围。本文将详细介绍折半查找算法的原理、实现以及应用场景。一、原理折半查找算......
  • 判断二分图的方法
    题目描述：龙龙得知2020年中国将有2000万至4000万男人娶不到老婆后。他打算好好调查一下是不是人们的感情出现问题。他对n个人进行调查，得到m条信息，每条信息表示为某两人曾经是情侣。由于他不知道这些人的性别，请你帮他判断一下，有没有同性是情侣的情况？对于100%的数据，n的范围[2,100000......
  • 二分模板
    整数二分边界boolcheck(intx){/*...*/}//检查x是否满足某种性质//区间[l,r]被划分成[l,mid]和[mid+1,r]时使用：intbsearch_1(intl,intr){while(l<r){intmid=l+r>>1;if(check(mid))r=mid;//check()判断mid是......
  • 算法0506 对数器 二分搜索
    对数器非常重要的自我验证代码正确性的方法在面试时或机试时写算法题，没有测试用例或者测试用例太少，导致巨大的数据量无法进行测试时。需要自己写测试用例数据时可以使用对数器。......
  • 学习C语言心得-自定义函数-对整形有序数组进行二分查找-二分法
    对整形有序数组进行二分查找#include<stdio.h>intfind(intarr[],intsz,intk){ intleft=0;intright=sz-1; while(left<=right) { intmid=left+right/2; if(k>arr[mid]) { left=mid+1; } if(k<arr[mid]) { right=mid......
  • 备忘录模式
      ......
  • 二分查找（浮点二分）
    一、算法简介浮点数二分相比与整数二分就要简单很多了，但是还是要注意范围的问题。以下给出一个小例子，求\(x\)的平方根，\(x\)的范围在\([0,10000]\)内：#include<iostream>#include<cmath>usingnamespacestd;intmain(){doublen;cin>>n;dou......
  • LeetCode704. 二分查找
    描述给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。示例1输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4示例2输入:nums=[-1,0,3,5,9,1......
  • 【二分图】第1幕：初识
    二分图的概念第1幕·第1场·二分图的概念定义若有一个无向图，其所有节点可以被分为两个不相交的非空集合，且同一集合中的点之间没有边，那么称该图为二分图。形式化地，对于一张图\(G=\{V,E\}\)，若有集合\(A,B\)满足：\((A,B\subseteqV)\and(A\capB=\emptyset)=1\)\(\fora......
  • 二分答案作题心得
    使用洛谷P1873举例看出这个题目考的是二分答案找出题目横纵坐标，横坐标是我们要输出的东西(也是L和R)，纵坐标是输入的m，理解题目，观察横纵坐标的递增递减关系这个题目里面输入的m是所得到的木材，横坐标是锯片的高度，锯片越高得到的木材越少，所以是递减关系开始写二分模板，写check函......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99