网站域名类型,天津做网站的,唐山模板建站系统,从搜索引擎访问网站目录
二分图是什么
acwing-860染色法判定二分图
染色法
代码
acwing-861二分图的最大匹配
思路
代码 二分图是什么
学习二分图的目的就是一些题目可以简化成二分图的模型来求解。
二分图也就是#xff1a;一个无向图顶点集#xff0c;分成了两堆顶点(可以理解为两…目录
二分图是什么
acwing-860染色法判定二分图
染色法
代码
acwing-861二分图的最大匹配
思路
代码 二分图是什么
学习二分图的目的就是一些题目可以简化成二分图的模型来求解。
二分图也就是一个无向图顶点集分成了两堆顶点(可以理解为两种不同性质)图中的每条边的两个端点分别属于两个不同的顶点集合。这两个顶点集内部顶点之间没有边所有的边都是连接两个不同顶点集合内的顶点。 一个图是二分图当且仅当它不包含奇环图。(这句话正反都成立。
奇环图就是存在边数是奇数的环 的图。
正向解释假设存在一个奇数长度的环那么环上的节点一定是交替属于两个集合的由于环的长度是奇数环的最后一个节点又必须与环的起始节点相连且它们属于同一个集合这与二分图的定义相矛盾。因此如果图是二分图则不可能存在奇数长度的环。
反之如果一个图不包含奇环那么我们通过染色法(后面会说)遍历图中的每一个节点相邻两个节点染色不同如果最终没有发生染色冲突的情况(即相邻的节点被染成了相同的颜色)那么就证明该图是二分图。
acwing-860染色法判定二分图 染色法
上面简单提过其实叫染色法也只是一种标记而已不用想的太复杂。
我们遍历图中的每个节点将其染色由于一个点染色之后与其相直连的其他顶点应该染什么色应该是固定的对吧因为二分图的定义嘛如果这个点还没被染色就染成与该点不同的颜色如果已经被染过色就判断所染的颜色是否与该点的颜色相同。 如果发现有冲突就说明不是二分图直接跳出循环。
我们这里采用深度优先遍历递归地对节点及其相邻节点进行染色并且检查相邻节点是否与当前节点的颜色相同。
代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N1e510,M2e510;
int n,m;
int h[N],e[M],ne[M],idx;
int color[N];//用俩标记是否被染色
void add(int x,int y)
{e[idx]y;ne[idx]h[x];h[x]idx;
}
bool dfs(int u,int c)//c表示该点被染的颜色
{color[u]c;for(int ih[u];i!-1;ine[i]){int je[i];if(!color[j]){if(!dfs(j,3-c))return 0;}else if(color[j]c)return 0;}return 1;
}
int main()
{cinnm;memset(h,-1,sizeof h);while(m--){int u,v;cinuv;add(u,v);//无向图add(v,u);}bool flag1;//作为标记for(int i1;in;i)//遍历所有顶点{if(!color[i])//如果该点没有被染色{if(!dfs(i,1))//就通过dfs将其染色并判断染色是否存在冲突{flag0;break;}}}if(flag)puts(Yes);else puts(No);return 0;
}
3-c作为染色是因为我们这里用1 2分别表示染成的两种不同的颜色而3-c刚好能够得到与前一个点的c不同的颜色。
acwing-861二分图的最大匹配 思路
首先要搞清楚匹配的概念 可以直白地理解为最多能有几对 一对一 的边。 为了尽可能的得到最大的匹配数有增广路径的概念嗯
我这里按照图中说一下比如1号点最开始应该直接匹配的是4号点但是在对3号点进行匹配的时候我们发现3号点只能与1号点匹配于是我们就想让1号点再找找有没有其他可以选择的(3号点只有1号只好让1号点变一变啦)发现1号点还可以与6号点匹配那这样就皆大欢喜啦我们多了一个匹配数。如果1号点也只有4号点能匹配那最大匹配数就只有2啦。
所以我们这里的思路就是只看左侧顶点寻找可以与其匹配的右侧顶点。注意每次开始针对一个左侧顶点寻找之前先把右侧顶点的标记都初始化一下避免与之前的标记混淆。
find函数的主要思路就是遍历这个左侧顶点直连的右侧顶点观察其是否已经被访问过。未被访问的情况下我们尝试为其寻找匹配的左侧顶点。[注意这里的思路是为右侧顶点寻找可以匹配的左侧顶点] 有两种可能的情况①该右侧顶点未被匹配过 ②该右侧顶点已经在前面几轮被匹配过了名花有主了 - ①如果右侧顶点 j 尚未匹配即 match[j] 0那么我们直接将其匹配给当前左侧顶点 x并返回 1。 - ②如果右侧顶点 j 已经匹配了一个左侧顶点 y(即 match[j] 不为 0)我们需要尝试找到另一个左侧顶点与右侧顶点 j 匹配(递归调用)。 为了实现上述所说的处理冲突以得到更大的匹配数的目的我们定义match数组其下标表示右侧顶点数组存储的是右侧顶点所对的左侧顶点当遇到了所谓的“冲突”我们就再找找该右侧顶点所对的左侧顶点是否还有其他的顶点可以匹配。
代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N510,M1e510;
int n1,n2,m;
int h[N],e[M],ne[M],idx;//由于我们只考虑左侧的点因此采用邻接表存储是合理的
int match[N];//记录右侧顶点匹配的左侧顶点编号下标表示右侧顶点 match数组表示的是左侧顶点
bool st[N];//标记右侧顶点是否已经被访问
void add(int u,int v)
{e[idx]v;ne[idx]h[u];h[u]idx;
}
bool find(int x)
{for(int ih[x];i!-1;ine[i]){int je[i];if(!st[j])//先检查右侧顶点 j 在这一轮中是否被访问过{st[j]1;if(match[j]0 || find(match[j])){match[j]x;return 1;}}}return 0;
}
int main()
{cinn1n2m;memset(h,-1,sizeof h);while(m--){int u,v;cinuv;add(u,v);//因为只需要遍历左侧顶点}int res0;for(int i1;in1;i)//遍历左侧节点{memset(st,0,sizeof st);//以便重新标记每个右侧顶点的访问状态不会受到之前搜索状态的影响if(find(i))res;}coutres;return 0;
}
上面思路明白之后代码应该不难理解。 写到这里。感觉时间好像有点紧。。嗯
有问题欢迎指出一起加油
