二分图Bipartite Graph
定义：
二分图又称作二部图，是图论中的一种特殊模型。
设G=(V,E)是一个无向图。如果顶点集 V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在 X中，另一个在Y中，则称图G为二分图。
性质
当且仅当无向图G的每一个环的结点数均是偶数时，图G才是一个二分图。
如果无环，相当于每的结点数为0，故也视为二分图
判定
如果一个图是连通的，可染色法判定是否二分图：
【假设】把X部的结点颜色设为0，Y部的颜色设为1。
- 从某个未染色的结点
u开始，做BFS或者DFS。 - 把
u染为0，枚举u的儿子v。- 如果
未染色，就染为与u相反的颜色， - 如果
已染色，则判断u与v的颜色是否相同，相同则不是二分图。
- 如果
- 如果一个图不连通，则在每个
连通块中作判定。
也就是说，同一部的顶点之间不应该有边
存储结构：无向图
struct Edge
{
int to;
Edge* next = NULL;
int w;//权值
};
class UndirectedGraph
{
public:
int n;
Edge* head[N];
void init(int n,int e)
{
//n代表左部点的个数，m代表右部点的个数,e代表边的条数
this->n = n;
for (int i = 0; i < n; i++)
{
head[i] = (Edge*)malloc(sizeof(Edge));
head[i]->next = NULL;
head[i]->to = 0;
}
while (e--)
{
int s, t;
cin >> s >> t;
Edge* now1;
Edge* now2;
now1 = (Edge*)malloc(sizeof(Edge));
now2 = (Edge*)malloc(sizeof(Edge));
now1->to = t;
now2->to = s;
now1->next = this->head[s]->next;
now2->next = this->head[t]->next;
this->head[s]->next = now1;
this->head[t]->next = now2;
}
return;
}
};判定函数
bool DFS(UndirectedGraph G, vector<int>& color, int v)
{
//对联通子图进行染色检查
for (Edge* now = G.head[v]->next; now != NULL; now = now->next)
{
if (color[now->to] == 0)
{
color[now->to] = color[v] % 2 + 1;//染上不同的颜色
if (!DFS(G, color, now->to))
return false;
}
else
{
if (now->to != v && color[now->to] == color[v])//如果搜到一条颜色相同的边
{
return false;
}
}
}
return true;
}
bool Is_BiPartGraph(UndirectedGraph G)
{
//染色法判断二分图
//用DPS搜
vector<int> color(G.n);
for (int i = 0; i < G.n; i++)
color[i] = 0;
for (int i = 0; i < G.n; i++)
{
if (color[i] == 0)
{
color[i] = 1;
if (!DFS(G, color, i))
return false;
}
}
return true;
}主函数
int main()
{
UndirectedGraph G;
int n, e;
cin >> n >> e;
G.init(n, e);
std::cout << Is_BiPartGraph(G);
return 0;
}测试数据
6 6
0 3
0 5
1 3
1 4
1 5
2 5 输出
1匹配
匈牙利算法
【预备】增广路径
【预备】反色
算法
-
初始化visit[]=0，match[]=0 -
for\ u∈第一部 -
初始化visit[]=0 为什么
visit[] ,每次都需要初始化一下？其实
visit[] 有点像：前面点看上的匹配对象，后面的点不能再抢了 -
bool maxmatch(int u)
-
for \ v∈u的邻接点 -
$visit[v]=1 -
$match[v]=u 为什么改的不是
match[u] 呢？两个都改会造成死循环 我们其实只给右侧配对 $return\ True$ -
$if\ 原来的match[v]这个点可以找到新的匹配点 $match[v]=u$ $return\ True$
-
-
-
return \ False
-
-
代码
struct Edge
{
int to;
Edge* next = NULL;
int w;//权值
};
class BiPartGraph
{
private:
Edge* head[N];
int n;
int m;
int e;
int visit[N];
int match[N];
bool maxmatch(int v);
public:
void init(int n,int m,int e);
int MaxMatch();
};int BiPartGraph::MaxMatch()
{
int ans = 0;
memset(this->visit, 0, sizeof(this->visit));
memset(this->match, 0, sizeof(this->match));
for (int i = 1; i <= this->n; i++)
{
**memset(this->visit, 0, sizeof(this->visit));**
if (maxmatch(i))
ans++;
}
return ans;
}
bool BiPartGraph::maxmatch(int v)
{
for (Edge* now = this->head[v]->next; now != NULL; now = now->next)
{
if (!this->visit[now->to])
{
visit[now->to] = 1;
if (!this->match[now->to] || this->maxmatch(this->match[now->to]))
{
match[now->to] = v;
return true;
}
}
}
return false;
}
void BiPartGraph::init(int n,int m,int e)
{
//n代表左部点的个数，m代表右部点的个数,e代表边的条数
this->n = n;
this->m = m;
this->e = e;
for (int i = 0; i < n + m + 5; i++)
{
head[i] = (Edge*)malloc(sizeof(Edge));
this->head[i]->to = 0;
this->head[i]->next = NULL;
}
while (e--)
{
//把n个点存在前面，m个点存在后面
int s, t;
cin >> s >> t;
t = this->n + t;
Edge* now1;
Edge* now2;
now1 = (Edge*)malloc(sizeof(Edge));
now2 = (Edge*)malloc(sizeof(Edge));
now1->to = t;
now2->to = s;
now1->next = now2->next = NULL;
Edge* now = this->head[s];
while (now->next != NULL)
{
if (now->to == t)
break;
else
now=now->next;
}
if (now->to != t && now->next == NULL)
{
now->next = now1;
}
now = this->head[t];
while (now->next != NULL)
{
if (now->to == s)
break;
else
now=now->next;
}
if (now->to != s && now->next == NULL)
{
now->next = now2;
}
}
return;
}int main()
{
BiPartGraph G;
int n, m, e;
cin >> n >> m >> e;
G.init(n, m, e);
cout << G.MaxMatch();
return 0;
}解题记录
二分图最优匹配：
【预备】最大权匹配：
使所选边权和最大的匹配
【预备】完全匹配（完备匹配）：
若X部和Y部中所有的顶点都是匹配M中的端点，则称M为完全匹配
完备匹配下的最大权匹配
【预备】可行顶标
可行顶标数组是人为添加的两个数组，一般为
初始化
一般来说，在初始状态下，选择顶点较少的部分作为
关于这个数组具体的使用方法，我们在后面讨论
性质
- 对于原图中的任意一条边
edge(x,y) 满足
-
相等子图相等子图是原图的一个生成子图,并且该生成子图只包含满足lx[x]+ly[y]=weight(x,y) 的边生成子图：包含原图中的所有结点，但是不包含所有的边的子图 最佳二分匹配如果原图的一个相等子图中包含完备匹配，那么这个匹配就是原图的最佳二分匹配
int bfs(int u)
{
tail=head=0;que[0]=u;
pre[u]=0;
while(tail<=head){
u=que[tail++];vis[u]=1;
for(reg int i=num_left+1;i<=num_right;i++)if(G[u][i]==lw[u]+lw[i]){
if(vis[i]) continue;
vis[i]=1;
if(match[i]) pre[match[i]]=u,que[++head]=match[i];
else{
int d=u,e=i,t;
while(d){
t=match[d];
match[d]=e;match[e]=d;
d=pre[d];e=t;
}
return 1;
}
}
}
return 0;
}
long long max_match()
{
for(reg int i=1;i<=num_left;i++){
for(reg int j=num_left+1;j<=num_right;j++) lw[i]=std::max(lw[i],G[i][j]);
}
for(reg int i=1;i<=num_left;i++){
std::memset(vis,0,sizeof vis);std::memset(d,0x7f,sizeof d);
if(bfs(i)) continue;
for(reg int j=1;j<=num_left;j++)if(vis[j])
for(reg int k=num_left+1;k<=num_right;k++)
if(!vis[k]) d[k]=std::min(d[k],lw[j]+lw[k]-G[j][k]);
while(1){
int now=1e9,to,s;
for(reg int j=num_left+1;j<=num_right;j++)if(!vis[j]) now=std::min(now,d[j]);
for(reg int j=1;j<=num_left;j++)if(vis[j]) lw[j]-=now;
for(reg int j=num_left+1;j<=num_right;j++)
if(vis[j]) lw[j]+=now;
else d[j]-=now,to=d[j]?to:j;
if(!match[to]) break;
s=match[to];vis[to]=vis[s]=1;
for(reg int j=num_left+1;j<=num_right;j++)
if(!vis[j]) d[j]=std::min(d[j],lw[s]+lw[j]-G[s][j]);
}
std::memset(vis,0,sizeof vis);
bfs(i);
}
LL ans=0;
for(reg int i=1;i<=num_right;i++) ans+=lw[i];
return ans;
}
int main()
{
num_left=read();num_right=read();m=read();
int nnn=num_left;
num_left=num_right=std::max(num_left,num_right);
num_right+=num_left;
for(reg int u,v,i=1;i<=m;i++){
u=read();v=read()+num_left;G[u][v]=G[v][u]=read();
}
std::printf("%lld\n",max_match());
for(reg int i=1;i<=nnn;i++)
std::printf("%d ",(match[i]&&G[i][match[i]])?(match[i]-num_left):0);
return 0;
}