【学习笔记】二分图基础
二分图与网络流基础（网络流待学）
查看目录
- 前置知识：
- 二分图：
- 二分图的定义：
- 二分图的判定：
- 例题：[NOIP2010 提高组] 关押罪犯
- 二分图的匹配：
- 匈牙利算法：
- 例题：[ABC317G] Rearranging
前置知识：
-
tarjan
-
强连通分量:有向图中几个点可以相互到达,就称这几个点是强连通分量。
-
点双连通分量: 删掉一个点后子图仍为强连通分量。
-
边双连通分量：删掉一条边子图仍为强连通分量。
-
奇环:指点的数量为奇数的简单环(简单环即没有重复边的环路)。
二分图：
二分图的定义：
对于一无向图，将该图分为两个点集，点集内部的点两两没有连边，则称该无向图为二分图，两个点集则是二分图的左部或右部。
较为数学的表示：
如果一张无向图 \((V,E)\) 存在点集 \(A,B\)，满足 \(|A|,|B| \ge 1\)，\(A \cap B = \varnothing\)，\(A \cup B = V\)，且对于 \(x,y \in A\) 或 \(x,y \in B\)，\((x,y) \notin E\)，则称这张无向图为一张二分图，\(A,B\) 分别为二分图的左部和右部。
二分图的判定：
一张图是二分图，当且仅当图中无奇环。
证明：每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。
因此可以考虑 \(dfs\) 染色，时间复杂度 \(O(n)\)，有代码：
Miku's Code
int n,m;
bool vis[maxn];
int head[maxn<<1],t;
struct edge{
int u,v;
int next_;
};edge e[maxn<<1];
void add_edge(int u,int v){
e[++t].u=u;
e[t].v=v;
e[t].next_=head[u];
head[u]=t;
}
bool dfs(int now){
vis[now]=true;
for(int i=head[now];i;i=e[i].next_){
int to=e[i].v;
if(vis[to]==true) return false;
dfs(to);
}
return true;
}
void input(){
scanf("%d %d",&n,&m);
int u,v;
for(int i=1;i<=m;++i){
scanf("%d %d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
}
int main(){
input();
if(dfs(1)) printf("YES\n");
else printf("NO\n");
return 0;
}
例题：[NOIP2010 提高组] 关押罪犯
题目链接
[NOIP2010 提高组] 关押罪犯
折叠题面
题目描述
S 城现有两座监狱，一共关押着 \(N\) 名罪犯，编号分别为 \(1-N\)。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 \(c\) 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 \(c\) 的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了\(N\) 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式
每行中两个数之间用一个空格隔开。第一行为两个正整数 \(N,M\)，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 \(M\) 行每行为三个正整数 \(a_j,b_j,c_j\)，表示 \(a_j\) 号和 \(b_j\) 号罪犯之间存在仇恨，其怨气值为 \(c_j\)。数据保证 \(1<a_j\leq b_j\leq N, 0 < c_j\leq 10^9\)，且每对罪犯组合只出现一次。
输出格式
共 \(1\) 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。
样例 #1
样例输入 #1
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
样例输出 #1
3512
提示
【输入输出样例说明】罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 \(3512\)（由 \(2\) 号和 \(3\) 号罪犯引发）。其他任何分法都不会比这个分法更优。
【数据范围】
对于 \(30\%\)的数据有 \(N\leq 15\)。
对于 \(70\%\) 的数据有 \(N\leq 2000,M\leq 50000\)。
对于 \(100\%\) 的数据有 \(N\leq 20000,M\leq 100000\)。
解题：
这道题可以用并查集做，这里说二分图做法。
一共两座监狱，而且要求监狱内的的矛盾较小，较为明显的二分图做法。
可以用两种颜色去标记图中的点，当一个节点被标记了一种颜色，与其相邻的点就是另一种颜色。
对于矛盾值，二分答案，大于等于枚举的答案的仇恨值连为一条边。
Miku's Code
#include<bits/stdc++.h>
using namespace std;
#define rg register int
#define il inline
typedef long long ll;
typedef long double llf;
const double eps=1e-8;
namespace mystd{
il int Max(int a,int b)<%if(a<b) return b;return a; %>
il int Min(int a,int b)<%if(a>b) return b;return a; %>
il int Abs(int a)<% if(a<0) return a*(-1);return a; %>
il double fMax(double a,double b)<%if(a<b) return b;return a; %>
il double fMin(double a,double b)<%if(a>b) return b;return a; %>
il double fAbs(double a)<% if(a<0) return a*(-1);return a; %>
il int dcmp(double a){
if(a<-eps) return -1;
if(a>eps) return 1;
return 0;
}
}
const int maxn=1e6+7;
int n,m,l,r;
int vis[maxn];
int head[maxn<<1],t;
struct edge{
int u,v,w;
int next_;
};edge e[maxn<<1];
void add_edge(int u,int v,int w){
e[++t].u=u;
e[t].v=v;
e[t].w=w;
e[t].next_=head[u];
head[u]=t;
}
bool check(int mid){
memset(vis,0,sizeof(vis));
queue<int> q;
while(!q.empty()) q.pop();
for(int i=1;i<=n;++i){
if(!vis[i]){
q.push(i);
vis[i]=1;
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i;i=e[i].next_){
if(e[i].w>=mid){
if(!vis[e[i].v]){
q.push(e[i].v);
if(vis[now]==1) vis[e[i].v]=2;
else vis[e[i].v]=1;
}
else if(vis[e[i].v]==vis[now]) return false;
}
}
}
}
}
return true;
}
void input(){
scanf("%d %d",&n,&m);
int u,v,w;
for(int i=1;i<=m;++i){
scanf("%d %d %d",&u,&v,&w);
r=mystd::Max(r,w);
add_edge(u,v,w);
add_edge(v,u,w);
}
}
int main(){
input();
int ans=0;
r=r+1;
while(l+1<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
printf("%d\n",l);
return 0;
}
二分图的匹配：
给定⼀个⼆分图 \(G\)，\(M\) 为 \(G\) 边集的⼀个⼦集，如果满⾜当中的任意两条边都不依附于同⼀个顶点（没有公共端点），则称 \(m\) 是⼀个匹配。
例如：
该图的#9999ff 色边集合和 #ff407a 色边集合均为二分图的匹配。
- 匹配点：
匹配边上的点就是匹配点。
- 二分图的最大匹配：
图中包含 边数最多 的匹配称为二分图的最大匹配。
- 完美匹配：
图中所有点都在匹配边上（即所有点均为匹配点），就称其为完美匹配，如上图的两个匹配均为完美匹配。
匈牙利算法：
定义说明：
- 交错路：始于非匹配点，由非匹配边和匹配边交错组成的路径。（如下图，空心点和实心点分别表示二分图的两个点集，同一点集内点不能连边，#ff407a 色边是匹配边）
- 增广路：始于非匹配点，终于非匹配点的交错路，路径长度一定为奇数。（如下图）
- 增广：对于增广路，其非匹配边比匹配边多 \(1\)，将匹配边改成非匹配边，非匹配边改成匹配边，则匹配边数加 \(1\)，且依然是交错路，此过程称为增广。（如上图变为上上图的过程）
核心思想：枚举所有非匹配点，找增广路，对每一条增广路取反，直到找不到增广路。
算法实现：
-
贪心，搜索递归。
-
将匹配边集合置为空。
-
找到一个增广路径 \(P\)，\(P\) 上的增广路全部取反得到一个更大的匹配。
-
重复上一步直到找不到增广路。
算法演示：如图：
Miku's Code
#define rg register int
int n,ans;
bool vis[831],g[831][831],match[831];
bool find(int x){
for(rg j=1;j<=n;++j){
if(!vis[j] && g[x][j]){
//x连向的所有点，若存在边且未标记过，因为是二分图，所以假设x在左边点集，j一定在右边点集
vis[j]=true;
int t=match[j];//右集合其匹配对象
if(!t || find(t)){
//如果没有对象就可以和x匹配，有则尝试更改对象，能更改就和x匹配，否则就返回false
match[j]=x;
return true;
}
}
}
else return false;
}
int main(){
scanf("%d",&n);
int ans=0;
for(rg i=1;i<=n;++i){
memset(vis,false,sizeof(vis));
if(find(i)) ++ans;
}
printf("%d\n",ans);
return 0;
}
时间复杂度：\(O(nm)\)。
例题：[ABC317G] Rearranging
题目链接
[ABC317G] Rearranging
折叠题面
[ABC317G] Rearranging
题目描述
$ N $ 行 $ M $ 列のグリッドがあります。上から $ i $ 行目左から $ j $ 列目のマスには整数 $ A_{i,j} $ が書かれています。
ここで、グリッドのマスに書かれている計 $ NM $ 個の整数は $ 1,\ldots,N $ をちょうど $ M $ 個ずつ含みます。
あなたは次の手順でマスに書かれた数を入れ替える操作を行います。
- $ i=1,\ldots,N $ の順に次を行う。
- $ i $ 行目に書かれた数を自由に並び替える。すなわち、$ 1,\ldots,M $ の並び替えである長さ $ M $ の数列 $ P=(P_{1},\ldots,P_{M}) $ を自由に選び、$ A_{i,1},\ldots,A_{i,M} $ を 同時に $ A_{i,P_{1}},\ldots,A_{i,P_{M}} $ に置き換える。
あなたの目的は、操作後に全ての列が $ 1,\ldots,N $ を $ 1 $ つずつ含むようにすることです。そのようなことが可能であるか判定し、可能であれば操作後のグリッドの状態を出力してください。
翻译：（提供：我）
现有一个 \(N\) 行 \(M\) 列的矩阵，从上往下数第 \(i\) 行，从左往右数第 \(j\) 列的元素是 \(A_{i,j}\)。
对于 \(i=1,\ldots,n\)，你可以自由排列第 \(i\) 行的数字。
要求每一列包含 \(1,\ldots,N\) 一次（不要求顺序，包含即可），若可能，输出 Yes，并打印结果表格，否则，输出 No。
输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ M $ $ A_{1,1} $ $ \ldots $ $ A_{1,M} $ $ \vdots $ $ A_{N,1} $ $ \ldots $ $ A_{N,M} $
输出格式
操作により全ての列が $ 1,\ldots,N $ を $ 1 $ つずつ含むようにするのが不可能ならば No と出力せよ。
可能であるとき、$ 1 $ 行目に Yes と出力し、続く $ N $ 行に、全ての列が $ 1,\ldots,N $ を $ 1 $ つずつ含むように操作したあとのグリッドの状態を次の形式で出力せよ。
グリッドの上から $ i $ 行目左から $ j $ 列目のマスに書かれた数を $ B_{i,j} $ とする。各 $ 1\leq\ i\ \leq\ N $ について $ i+1 $ 行目に $ B_{i,1},\ldots,B_{i,M} $ をこの順に空白区切りで出力せよ。
答えが複数存在する場合、どれを出力しても正解とみなされる。
样例 #1
样例输入 #1
3 2
1 1
2 3
2 3
样例输出 #1
Yes
1 1
3 2
2 3
样例 #2
样例输入 #2
4 4
1 2 3 4
1 1 1 2
3 2 2 4
4 4 3 3
样例输出 #2
Yes
1 4 3 2
2 1 1 1
4 2 2 3
3 3 4 4
提示
制約
- $ 1\ \leq\ N,M\ \leq\ 100 $
- $ 1\ \leq\ A_{i,j}\ \leq\ N $
- 入力は全て整数である
- $ NM $ 個の数 $ A_{1,1},\ldots,A_{N,M} $ は $ 1,\ldots,N $ をそれぞれちょうど $ M $ 個ずつ含む
Sample Explanation 1
この他、以下の出力も正解とみなされる。 Yes 1 1 2 3 3 2
解题：
其实官方题解写的还是很清楚的。（但是思路好难想啊~）
我们建立二分图的子集，左边的子集代表 \(1,\ldots,n\) 行，右边的子集代表 \(1,\ldots,n\) 个数，共 \(2n\) 个点，显然子集内点没有连边，它是二分图。
而该行内有哪些数就从左子集的代表行的点连向右子集代表数的点连边，有几个连几次。
如样例 #1：
input:
3 2
1 1
2 3
2 3
因此可以找一个图的最大匹配，对于某一列，我们就得到了其数，如#9999ff 色边，其为一列：
1
2
3
然后再删去已经找到过的边，继续找最大匹配，即可。
output:
Yes
1 1
3 2
2 3