2020.5.27 刚学完二分图感觉总结一下比较好,图论确实让人头秃,差不多一个多星期大概理解了二分图的内容,但还是挺生涩,还是多打点题吧 由于第一次学可能有些地方有出错欢迎大家指正! 2020.8.22 再次和二分图不期而遇,这次学完了二分图最大权匹配、覆盖、独立集的内容,还给别人讲课理解的较为透彻,故决定完善此博客,我也是从小白过来的,明白自学找博客找教学很累,网上的东西参差不齐,所以我尽量用易懂的方式介绍二分图的知识,可能会比较长,希望可以耐心看下去,相信你一定会有所收获的!
二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。(简单说就是把一个图的顶点分成两个集合,且集合内的点不邻接)
1.匹配:给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。 2.极大匹配:指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。 3.最大匹配:所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。 4.完全匹配(完备匹配):一个匹配中,图中的每个顶点都和图中某条边相关联。(最大权匹配会碰到这个概念,mark一下)
个人理解:两个顶点很好理解,毕竟一个点也不能配对。无回路也可以很容易把点分成两个无关的集合。有回路时,如果回路为奇数 (图2)无论如何不能分成两个无关联的集合,故不是二分图,偶数则可以(图1)。
严谨证明通过反证法,先假设有回路且回路为奇数,最后会发现矛盾。
下面用邻接表法分别给出dfs和bfs的代码
const int maxn = 1e5+10;
vector <int> G[maxn];
int col[maxn];
bool bfs(int u)//这里因为不一定连通图的原因设置一个变量,外部引用函数的时候遍历访问就行
{
queue<int> q;
q.push(u);//当前点入队
col[u]=1;//当前点涂色
while(!q.empty())
{
int v=q.front();
q.pop();
for(int i=0;i<G[v].size();i++)//遍历与当前点关联的所有点
{
int x=G[v][i];//获得第i个关联点的下标
if(col[x]==0)//如果没图色
{
col[x]=-col[v];//图相反颜色
q.push(x);
}
else
{
if(col[x]==col[v])//颜色相同不是二分图返回false
return false;
}
}
}
return true;
}
void solve()
{
for(int i=1;i<=n;i++)
{
if(col[i]==0&&!bfs(i))
{
printf("No\n");
return;
}
}
printf("Yes\n");
}
bool dfs(int v, int c){
color[v] = c; //将当前顶点涂色
for(int i = 0; i < n; i++){ //遍历所有相邻顶点,即连着的点
if(edge[v][i] == 1){ //如果顶点存在
if(color[i] == c) //如果颜色重复,就返回false
return false;
if(color[i] == 0 && !dfs(i,-c)) //如果还未涂色,就染上相反的颜色-c,并dfs这个顶点,进入下一层
return false; //返回false
}
}
return true; //如果所有顶点涂完色,并且没有出现同色的相邻顶点,就返回true
}
红线代表匹配边, 1、5、4、7已匹配,则8->4->7->1->5为一条增广路
const int maxn = 1e5+10;
vector <int> G[maxn];
int n,m;//n为点的数量 m为边的数量
int vis[maxn],pei[maxn];//vis记录点是否被访问,pei存每个点所匹配的点
bool dfs(int u)
{
for(int i=0;i<G[u].size();i++)//遍历与该点关联的所有点
{
int v=G[u][i];//所关联的点
if(!vis[v])//没访问过
{
vis[v]=1;
if(!pei[v]||dfs(pei[v]))//若关联的点没被匹配或者dfs返回true说明关联的点所匹配的点可以挪走,则把关联的点和传入的点匹配(即下面代码)
{
pei[v]=u;
return true;
}
}
}
return false;
}
void solve()
{
int ans=0;
for(int i=1;i<=n;i++)//遍历所有的点
{
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;//如果有增广路则加一条匹配边
}
printf("%d\n",ans);
}
Fire Net HDU – 1045 这题还用到了缩点的原理 需要思考一下 The Accomodation of Students HDU – 2444 很裸的判断二分图+最大匹配
给定一张二分图,每条边都有一个权值。求出该二分图的一组最大匹配,使得匹配边的权值总和最大。
若相等子图中存在完备匹配,则这个完备匹配呼吁事故二分图的带权最大匹配。(KM算法的缺陷,只能求存在完备匹配的最大权匹配)
证明: 1.由于完备匹配包含二分图中所有的节点,根据相等子图的定义,这个完备匹配的边权之和等于所有顶标和 2.假设还有一个完备匹配,此完备匹配不完全等于相等子图,对于不在相等子图中的边,边权值一定小于两端点的顶标和,所有这个完备匹配的边权之和必定小于相等子图中的完备匹配,故相等子图中的完备匹配最大。
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL long long
using namespace std;
const int maxn = 1e3+10;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
int wx[maxn], wy[maxn]; //每个点的顶标值(需要根据二分图处理出来)
int matchx[maxn], matchy[maxn]; //每个点所匹配的点
int visx[maxn], visy[maxn]; //每个点是否加入增广路
int cntx = maxn, cnty = maxn; //分别是X和Y的点数
int mp[maxn][maxn]; //二分图边的权值
int d; //边权和顶标最小的差值
bool dfs(int u) //进入DFS的都是X部的点
{
visx[u] = 1; //标记进入增广路
for (int v = 0; v < cnty; v++) {
if (!visy[v] && mp[u][v] != INF)
{
int t = wx[u] + wy[v] - mp[u][v];
if (t == 0) // t为0说明是相等子图
{
visy[v] = 1;
if (matchy[v] == -1 || dfs(matchy[v])) {
matchx[u] = v;
matchy[v] = u; //进行匹配
return true;
}
}
else if (t > 0) //此处t一定是大于0,因为顶标之和一定>=边权
{
d = min(d, t); //边权和顶标最小的差值
}
}
}
return false;
}
int KM() {
memset(matchx, -1, sizeof(matchx));
memset(matchy, -1, sizeof(matchy));
memset(wx, 0, sizeof(wx)); // wx的顶标为该点连接的边的最大权值
memset(wy, 0, sizeof(wy)); // wy的顶标为0
for (int i = 0; i < cntx; i++) //预处理出顶标值
{
for (int j = 0; j < cnty; j++) {
if (mp[i][j] == INF) {
continue;
}
wx[i] = max(wx[i], mp[i][j]);
}
}
for (int i = 0; i < cntx; i++) //枚举X部的点
{
while (1) {
d = INF;
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (dfs(i)) break; //已经匹配正确
//还未匹配,将X部的顶标减去d,Y部的顶标加上d
for (int j = 0; j < cntx; j++)
if (visx[j]) wx[j] -= d;
for (int j = 0; j < cnty; j++)
if (visy[j]) wy[j] += d;
}
}
int ans = 0; //二分图最优匹配权值
for (int i = 0; i < cntx; i++)
if (matchx[i] != -1) ans += mp[i][matchx[i]];
return ans;
}
int n, k;
int main() {
int result = KM();
cout << result << endl;
return 0;
}
蓝色线代表该二分图的最大匹配,我们从左部所有的非匹配点出发,做一个增广路(必定失败,因为已经存在最大匹配了),标记经过的所有点(绿色为所有的左部非匹配点出发的增广路径),我们选取左边所有未被标记的点和右边所有被标记的点(红色方框),这几个点就是该二分图的一个覆盖,理由如下: 首先明确几个此构造的性质:
二分图的边可以分为匹配边和非匹配边两种。 – 对于匹配边:由于性质3,如果都被标记,那么左部点一定被选,如果都没被标记,则右部点一定被选,一共m个匹配,则最多有m个点被选。 – 对于非匹配边,分三种情况: – 左边非匹配点——右边匹配点,由构造方式可知,右边的匹配点一定被标记,所以右边被选中。 – 左边匹配点——右边非匹配点,假设左部匹配点被标记那么右边非匹配点一定也被标记,与性质2矛盾,所有左部点一定未被标记,那么左部点一定被选到了。 – 左边未匹配——右边未匹配:不存在,与最大匹配矛盾
综上可知,此构造法选出的是一个覆盖且覆盖的点数最多m个,即最小点覆盖<=最大匹配数。
由于最小点覆盖>=最大匹配数&&最小点覆盖<=最大匹配数,故最小点覆盖最大匹配数
如上图(左)的最小路径覆盖为:1->2->5, 3, 4(因为不能相交,所有路径数为3),我们很轻松的可以发现一个性质:每条路径的出度和入度都不超过1(因为不能相交) – 定理:拆点构造二分图:将DAG中每个点x拆成x和x+n两个点,分别作为一张新二分图的左部和右部,则 编号为1 – n的点为二分图左部,n+1 – 2n的点为右部,对于原图每条有向边(x,y), 在二分图的左部点x与右部点y+n之间连边,得到拆点二分图,记为G’(上图右),则最小路径覆 盖=原图点个数-G’的最大匹配数。 – 证明:由于每条路径的出度和入度都不超过1,所以每条路径对应二分图中的一个匹配(我们可以把二分图的左部看成出点,右部看成入点,每条原图的有向边都是从左部出点连向右部入点的,由于路径的性质,每个路径的出点和入点一 一对应,满足二分图匹配的性质),并且每条路径的终点必然对应一个左部的非匹配点。那么我们要让路径数最少,就是要让左部非匹配点最少,就是让二分图的匹配最多,所以最少路径数就等于原图点数减去二分图的最大匹配数。 – 最小路径可重复点覆盖:在一个有向无环图中(DAG)用最少的可相交的简单路径覆盖所有的点。 – 方法:先对DAG求一次传递闭包,然后当作求最小路径点覆盖。 – 原理:若两条路径相交,你们说明有两点a,b通过相交点连通,那么可以直接把ab 连接起来,跳过相交点,对所有的点都这样操作,然后要求路径不可相交,那么就 是最小路径点覆盖问题。 – floyd求传递闭包模板:
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (mp[i][k] && mp[k][j]) mp[i][j] = 1;
}
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL longlong
using namespace std;
const int maxn = 1e4 + 10;
bool vis[maxn];
int link[maxn];
vector<int> mp[maxn];
bool dfs(int x) {
for (int i = 0; i < mp[x].size(); ++i) {
int y = mp[x][i];
if (!vis[y]) {
vis[y] = true;
if (link[y] == -1 || dfs(link[y])) {
link[y] = x;
return true;
}
}
}
return false;
}
int hug(int n) {
int ans = 0;
for (int i = 0; i < n; ++i) {
memset(vis, false, sizeof(vis));
if (dfs(i)) ans++;
}
return ans;
}
int main(int argc, char const *argv[]) {
int n;
while (~scanf("%d", &n) && n) {
memset(link, -1, sizeof(link));
for (int i = 0; i < n; ++i) {
mp[i].clear();
}
for (int i = 0; i < n; ++i) {
int x, y, t;
scanf("%d:(%d)", &x, &t);
while (t--) {
scanf("%d", &y);
mp[x].push_back(y);
mp[y].push_back(x);
}
}
printf("%d\n", hug(n) / 2);
}
return 0;
}
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL longlong
using namespace std;
const int maxn = 1e4 + 10;
bool vis[maxn];
int link[maxn];
vector<int> mp[maxn];
bool dfs(int x) {
for (int i = 0; i < mp[x].size(); ++i) {
int y = mp[x][i];
if (!vis[y]) {
vis[y] = true;
if (link[y] == -1 || dfs(link[y])) {
link[y] = x;
return true;
}
}
}
return false;
}
int hug(int n) {
int ans = 0;
for (int i = 1; i <= n; ++i) {
memset(vis, false, sizeof(vis));
if (dfs(i)) ans++;
}
return ans;
}
int main(int argc, char const *argv[]) {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
memset(link, -1, sizeof(link));
for (int i = 0; i <= n; ++i) {
mp[i].clear();
}
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
mp[x].push_back(y);
}
printf("%d\n", n - hug(n));
}
return 0;
}
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define LL longlong
using namespace std;
const int MAXN = 310;
const int INF = 0x3f3f3f3f;
int nx,ny;//两边的点数
int g[MAXN][MAXN];//二分图描述
int linker[MAXN],lx[MAXN],ly[MAXN];//y中各点匹配状态,x,y中的点标号
int slack[MAXN];
bool visx[MAXN],visy[MAXN];
bool DFS(int x)
{
visx[x] = true;
for(int y = 0; y < ny; y++)
{
if(visy[y])continue;
int tmp = lx[x] + ly[y] - g[x][y];
if(tmp == 0)
{
visy[y] = true;
if(linker[y] == -1 || DFS(linker[y]))
{
linker[y] = x;
return true;
}
}
else if(slack[y] > tmp)
slack[y] = tmp;
}
return false;
}
int KM()
{
memset(linker,-1,sizeof(linker));
memset(ly,0,sizeof(ly));
for(int i = 0;i < nx;i++)
{
lx[i] = -INF;
for(int j = 0;j < ny;j++)
if(g[i][j] > lx[i])
lx[i] = g[i][j];
}
for(int x = 0;x < nx;x++)
{
for(int i = 0;i < ny;i++)
slack[i] = INF;
while(true)
{
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(DFS(x))break;
int d = INF;
for(int i = 0;i < ny;i++)
if(!visy[i] && d > slack[i])
d = slack[i];
for(int i = 0;i < nx;i++)
if(visx[i])
lx[i] -= d;
for(int i = 0;i < ny;i++)
{
if(visy[i])ly[i] += d;
else slack[i] -= d;
}
}
}
int res = 0;
for(int i = 0;i < ny;i++)
if(linker[i] != -1)
res += g[linker[i]][i];
return res;
}
int main()
{
int n;
while(scanf("%d",&n) == 1)
{
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
scanf("%d",&g[i][j]);
nx = ny = n;
printf("%d\n",KM());
}
return 0;
}
include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
const int INF = 0x3f3f3f3f;
int w[205][205];
int lx[205], ly[205];
int sx[205], sy[205];
int match[205], slack[205];
int path(int u) {
sx[u] = 1;
for (int i = 1; i <= N; ++i) {
if (sy[i]) continue;
int t = lx[u] + ly[i] - w[u][i];
if (!t) {
sy[i] = 1;
if (!match[i] || path(match[i])) {
match[i] = u;
return true;
}
} else {
slack[i] = min(slack[i], t);
}
}
return false;
}
void KM() {
memset(match, 0, sizeof (match));
memset(lx, 0x80, sizeof (lx));
memset(ly, 0, sizeof (ly));
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) {
lx[i] = max(lx[i], w[i][j]);
}
}
for (int i = 1; i <= N; ++i) {
memset(slack, 0x3f, sizeof (slack));
while (1) {
memset(sx, 0, sizeof (sx));
memset(sy, 0, sizeof (sy));
if (path(i)) break;
int d = INF;
for (int j = 1; j <= N; ++j) {
if (!sy[j]) d = min(d, slack[j]);
}
for (int j = 1; j <= N; ++j) {
if (sx[j]) lx[j] -= d;
if (sy[j]) ly[j] += d;
else slack[j] -= d;
}
}
}
int ret = 0;
for (int i = 1; i <= N; ++i) {
ret += w[match[i]][i];
}
printf("%d\n", -ret);
}
int main() {
int T, x, y, ct;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &N, &M);
memset(w, 0x80, sizeof (w));
for (int i = 1; i <= M; ++i) {
scanf("%d %d %d", &x, &y, &ct);
w[x][y] = max(w[x][y], -ct);
}
KM();
}
return 0;
}