二分图性质
这其实是非常常用的东西，今天把匈牙利重新补了一遍就写个博客
今天因为二分图吃了很大的亏于是找来一片博客好好研读一下，发现还是很有收获，虽然名词糊脸蛋比数学公式糊脸舒服的多，于是搬运过来
二分图各大概念
1. 二分图定义
假设图G=（V，E）是一个无向图，若顶点集 V 可以分解成两个互不相交的子集（A，B），并且图中的所有边（i，j）的点 i，j 分别属于子集 A，B 中的元素，则称图 G 是一个二分图。
2. 零散的小概念
- 匹配：无公共点的边集合。（形象点就是 X与Y之间的边的个数）
- 匹配数：边集中边的个数。
- 最大匹配：匹配数最大的匹配。
- 边独立集：指图中边集的一个子集，且该子集中的任意两条边之间没有公共点。（对比匹配的概念我们发现，其实边独立集和匹配是一个概念）
- 最大边独立集：包含边数最多的边独立集。（其实就是最大匹配，为了方便，以后统称最大匹配）
具体解释
如图，如果<1,4>是一个合法匹配，那么<1,5>就不是一个合法的匹配，因为它们有公共点1 。
同样的如果<2,5>是一个合法的匹配，那么<2,6>和<3,5>就不是一个合法的匹配。
不难看出，其中最大匹配是边集：{1， 4， 5}最大匹配数为3 。
这些概念都很基础，没啥用
3. 其他比较重要概念及结论
- 独立集：
是指图的顶点集的一个子集，且该子集中的任意两个顶点之间不存在边。如果一个独立集不是任何一个独立集的子集, 那么称这个独立集是一个极大独立集。
最大独立集：一个图中包含顶点数目最多的独立集称为最大独立集。
- 孤立点：
没有匹配边的点。（需要说明的是，实际上好像没有孤立点官方定义，我在这里用到，是想更直观的突出最大独立集）
根据独立集和匹配以及孤立点的定义，我们可以推断出，
独立集就是由孤立点和匹配边的一个端点所组成的
（其中，若在每个匹配中选择独立集的端点时，只选择X部或Y部，那么一定不会出错。但是，又有X部又有Y部，可能会出错，也可能不会出错）。
那么，我们就得到了一个求最大独立集的一个公式：
最大独立集 = 孤立点 + 最大匹配
注意，因为孤立点一般不做要求，所以，这个公式是用不到的。
事实上，我甚至不确定这个公式的正确性，不过，按定义来讲应该是正确的。
下面，我们会给出最大独立集的常用公式）。
如上图1，孤立点：{7}只有一个，
最大匹配：{1， 4，5}有三个。所以最大独立集个数 = 1 + 3 = 4 。
最大独立集：{1,2,3,7} 或 {4,5,6,7}。
- 支配集
是指图顶点集的一个子集，若设L是图G 的一个支配集，则对于图中的任意一个顶点u，
要么属于集合L，要么与L中的顶点相邻。 称图G的所有支配集中顶点个数最少的支配集为最小支配集。
通俗点讲，如果我们选中一个点，则称和这个相邻的所有点都被这个点覆盖了。
那么支配集，就是找出一些点来覆盖其他的点，
最小支配集就是用最小的点来覆盖所有的点
如图2，根据支配集的定义，不难看出{1, 2, 3, 4, 5}，{2, 5, 6, 7}，{2, 5}都是图2的支配集，其中{2，5}是最小支配集。
- 最小点覆盖, 最小边覆盖：
是指图的顶点集的一个子集，如果我们选中一个点，则称这个点将所有以它为端点的边都覆盖了。
将图中所有的边都覆盖并且用到的顶点数最少的集合就是最小点覆盖。
同样的，我们可以得出边覆盖的定义，边覆盖是指图的边集的一个子集，如果我们选中一条边，则称这条边将它 所连的所有端点都覆盖了。
将图中所有的点都覆盖并且用到的边数最少的集合就是最小边覆盖。
根据，最小点覆盖的定义。我们不难看出，
图中三种不同颜色的顶点就是最小点覆盖，
仔细观察，我们还知道，此图的最大匹配也刚好是3 。
其实，确实有个定理
最小点覆盖 = 最大匹配。
最小边覆盖 = 最大独立集 = 顶点总数 - 最大匹配数
- 路径覆盖
路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联。
其中，路径数目最少的就是最小路径覆盖。
对于路径覆盖，是针对有向图的，走过一条路径之后，不能返回来去走另一条。对于图4，不难看出，最小路径覆盖为 2 。{1,2,3}，{4}。
当然，你还可以选其他的，不过不管你怎么走，最后都必须至少要2条路径才能覆盖所有的点。
二分图重要结论
最小点覆盖 = 最大匹配}
最大独立集 = 顶点总数 - 最大匹配}
简单证明
我们先设：总顶点：V。孤立点：X。最大独立集：S。最大匹配：M。现在要证明的是：$$S=V-M$$成立。
我们知道，一个匹配对应连个两个端点，且没有公共点。故：$$V=2 M + X $$。
根据上面有公式：$$S = M + X$$
那么现在证明 $$S= V- M$$ 就转化为证明
$$M+X=2 M + X - M$$
显然，这是成立的。故得证。最小边覆盖 = 顶点总数 - 最大匹$
最小路径覆盖 = 顶点总数 - 最大匹配
证明：
我们先假设，最大匹配为0。那么图中不存在边，要想访问所有点，
就得有V条路径（V为总顶点数，单个顶点也算是一路径）。
如果有一个匹配，那么匹配这条路径就连了两个点，
故剩余的V-2个点需V-2条路径覆盖，
故为最小路径覆盖=V-1，那么，把匹配数推广到M条。可以得到最小路径覆盖 = V - M。最小路径覆盖=最大独立集=最小边覆盖=顶点总数-最大匹配
这是最重要的结论
运用于恶心例题
二分图匹配
首先是愉快的网络流算法
直接建一个超级源点和汇点，中间的点互相一连就行
#include <bits/stdc++.h>
#define N 1000003
using namespace std;
int head[N],deep[N];
int st,ed,cnt=-1,n,m,n1,m1,m0;
struct node
{
int to,w,fr;
int nt=-1;
}edge[N];
void add(int x,int y,int z)
{
cnt++;
edge[cnt].to=y;
edge[cnt].nt=head[x];
edge[cnt].w=z;
head[x]=cnt;
}
int bfs()
{
memset(deep,0,sizeof(deep));
queue<int> q;
q.push(st);
deep[st]=1;
while(!q.empty())
{
int tmp=q.front();
q.pop();
for(int i=head[tmp];i!=-1;i=edge[i].nt)
{
int v=edge[i].to;
if(deep[v]||edge[i].w<=0)continue;
deep[v]=deep[tmp]+1;
q.push(v);
}
}
if(deep[ed])return 1;
else return 0;
}
int dfs(int u,int flow)
{
if(u==ed)return flow;
int ans=0;
for(int i=head[u];i!=-1&&ans<flow;i=edge[i].nt)
{
int v=edge[i].to;
if(deep[v]!=deep[u]+1)continue;
if(!edge[i].w)continue;
int x=dfs(v,min(edge[i].w,flow-ans));
edge[i].w-=x;
edge[i^1].w+=x;
ans+=x;
}
return ans;
}
int dinic()
{
int sum=0;
while(bfs())
sum+=dfs(st,0x3fffff);
return sum;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n1,&m1,&m0);
st=1;ed=n1+m1+2;
for(int i=1;i<=n1;i++)
{
add(1,i+1,1);
add(i+1,1,0);
}
for(int i=1;i<=m0;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x>n1||y>m1)continue;
add(x+1,y+n1+1,1);
add(y+n1+1,x+1,0);
}
for(int i=1;i<=m1;i++)
{
add(i+1+n1,ed,1);
add(ed,i+1+n1,0);
}
printf("%d",dinic());
return 0;
}
匈牙利算法
总之就是强行匹配，没有就看能不能腾出来
#include <bits/stdc++.h>
#define N 60000
using namespace std;
int dis[1100][1100],vis[1100],match[1100],n,m,ans,t;
int head[N],deep[N];
int st,ed,cnt=1;
struct node
{
int nt,to,w;
}edge[2*N];
void add(int x,int y)
{
edge[++cnt]=(node){head[x],y,0};
head[x]=cnt;
}
int findf(int x)
{
if(vis[x]) return 0;
vis[x]=1;
for(int i=head[x];i;i=edge[i].nt)
{
int v=edge[i].to;
if(!match[v]||findf(match[v]))
{
match[v]=x;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x>n||y>m)continue;
add(x,y);
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(findf(i))ans++;
}
printf("%d",ans);
return 0;
}
最小路径覆盖——例题训练
根据二分图的性质：最小路径覆盖=最大独立集=最小边覆盖=顶点总数-最大匹配
关键在于记录所有的路径
我们选择运用并查集来记录。
对于每一条边，我们还需记录一个fr来精确判断有效边。
当遍历到的边的fr与to不在一个集合，就把
fa[edge[i].to-n]=fa[edge[i].fr];
(千万不要记反。。。)
最后顺着输出所有fa[i]=i的点就输出了所有的路径。
核心代码
for(int i=1;i<=n;i++)fa[i]=i; for(int i=2;i<=cnt;i++) { if(edge[i].w==0&&edge[i].to>n && edge[i].to<=n*2&&edge[i].fr>0&&edge[i].fr<=n) if(fa[edge[i].fr]!=fa[edge[i].to-n]) fa[edge[i].to-n]=fa[edge[i].fr]; } for(int i=1;i<=n;i++) if(fa[i]==i)print(i),putchar('\n');总代码
#include <bits/stdc++.h>
using namespace std;
const int inf=(1<<30);
const int N=6000;
int n,m,cnt=1,head[N],deep[N],st,ed,ans,fa[N];
int findf(int x)
{
if(x==fa[x])return x;
return fa[x]=findf(fa[x]);
}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node
{
int nt,to,w,fr;
}edge[N*3];
void add(int x,int y,int z)
{
edge[++cnt]=(node){head[x],y,z,x};head[x]=cnt;
edge[++cnt]=(node){head[y],x,0,y};head[y]=cnt;
}
int bfs()
{
memset(deep,0,sizeof(deep));
queue<int> q;
q.push(st);
deep[st]=1;
while(!q.empty())
{
int tmp=q.front();
q.pop();
for(int i=head[tmp];i;i=edge[i].nt)
{
int v=edge[i].to;
if(deep[v]||edge[i].w<=0)continue;
deep[v]=deep[tmp]+1;
q.push(v);
if(v==ed)return 1;
}
}
return 0;
}
int dfs(int u,int flow)
{
if(u==ed)return flow;
int rest=flow;
for(int i=head[u];i;i=edge[i].nt)
{
if(!rest) return flow;
int v=edge[i].to;
if(!edge[i].w)continue;
if(deep[v]!=deep[u]+1)continue;
int x=dfs(v,min(edge[i].w,rest));
if(!x)deep[v]=0;
edge[i].w-=x;
edge[i^1].w+=x;
rest-=x;
}
return flow-rest;
}
int dinic()
{
int sum=0;
while(bfs())
sum+=dfs(st,inf);
return sum;
}
void print(int x)
{
printf("%d ",x);
for(int i=head[x];i;i=edge[i].nt)
{
if(edge[i].w==0&&edge[i].to>n)
print(edge[i].to-n);
}
}
int main()
{
n=read();m=read();
st=0;ed=2*n+2;
for(int i=1;i<=m;i++)
{
int x,y;
x=read();y=read();
add(x,y+n,1);
}
for(int i=1;i<=n;i++)add(st,i,1);
for(int i=n+1;i<=n*2;i++)add(i,ed,1);
ans=dinic();
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=2;i<=cnt;i++)
{
if(edge[i].w==0&&edge[i].to>n && edge[i].to<=n*2&&edge[i].fr>0&&edge[i].fr<=n)
if(fa[edge[i].fr]!=fa[edge[i].to-n])
fa[edge[i].to-n]=fa[edge[i].fr];
}
for(int i=1;i<=n;i++)
if(fa[i]==i)print(i),putchar('\n');
printf("%d",n-ans);
return 0;
}