【图论】二分图最大匹配——匈牙利算法
二分图
相当好理解
这是百度百科的定义
二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图
听不懂吧
其实就是一个图能正好分成两部分,每个部分内的点互相没有边就是二分图
二分图的判定
用两种颜色,让相连的点的颜色不同就好啦
如果要染色的点已经有颜色了,并且和当前这个点的颜色相同,那么说明发生了矛盾,也就是这张图不是二分图
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
inline int read()
{
int w=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9')
{
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w*f;
}
bool check;
int n,m;
int tot;
int col[maxn];
int head[maxn];
struct edge
{
int to;
int next;
}e[maxn*2];
void add(int x,int y)
{
tot++;
e[tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
bool dfs(int x,int c)
{
col[x]=c;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(!col[to])
{
if(dfs(to,-c))
{
return true;
}
}
else if(col[to]==c)
{
return true;
}
}
return false;
}
int main()
{
n=read();
m=read();
for(int i=1;i<=m;i++)
{
int u=read();
int v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++)
{
if(!col[i])
{
check=dfs(i,1);
}
if(check==true)
{
break;
}
}
if(check)
{
cout<<"No";
}
else
{
cout<<"Yes";
}
return 0;
}
二分图最大匹配
匈牙利算法
很简单啦
先枚举左部点u,然后和右边的v匹配,如果当前的匹配的这个右部点v已经和另一个左部点w匹配了,就让原来匹配的左部点w换一个(他会同意的,除非他没有其他选择了),如果w没得换那u只能单着了(可怜)
代码很短,就是个dfs
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=5e4+5;
inline int read()
{
int w=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
{
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9')
{
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w*f;
}
int tot,ans;
int head[maxn];
int n,m,num_e;
int match[maxn];
bool vis[maxn];
struct edge
{
int to;
int next;
}e[maxn];
void add(int x,int y)
{
tot++;
e[tot].to=y;
e[tot].next=head[x];
head[x]=tot;
}
bool dfs(int x)
{
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(!vis[to])
{
vis[to]=true;
if(!match[to] || dfs(match[to]))
{
match[to]=x;
return true;
}
}
}
return false;
}
int main()
{
n=read();
m=read();
num_e=read();
for(int i=1;i<=num_e;i++)
{
int u=read();
int v=read();
add(u,v);
}
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(dfs(i))
{
ans++;
}
}
cout<<ans;
return 0;
}
标签:二分,ch,int,匈牙利,while,笔记,算法,include,getchar From: https://www.cnblogs.com/SitoASK/p/16714324.html生まれつき何も持っていないからこそ、私たちはすべてを持つことができます