图论–最小生成树本小章节的内容颇多但是董事很经典的内容由于主包也是一名实用主义所以不适用的知识我们也直接不讲了我们的最小生成树内容有如下啊图上也打对叉了这个Prim堆优化版本十分不常用一般都是用克鲁斯卡尔来代替因为克鲁斯卡尔时间复杂度比它快个常数倍然后苏里还很好理解。二分图也是一个很常考很重要的算法在这里一并讲解了。最小生成树Prim朴素版本克鲁斯卡尔二分图染色法匈牙利算法点击上方专辑试试呢最小生成树Prim朴素版本Prim算法是一个很经典的找最小生成树问题其板子如下P3366 【模板】最小生成树 - 洛谷其做法就是先建图这个图论的很多问题都是先建图之后直接进入Prim函数来运行那么我们的Prim怎么做呢首先我们把所有的点都初始化为INF只有点1的距离是0那么对于n个点我们遍历n次对于每一个点如果它没有被标记过并且它如果是找到的第一个没被标记的点或者这个点比上一个点距离更加近那么我们就把指针变到j最后如果没找到或者这个点的距离是正无穷那么肯定是不符合题意的直接退出函数输出orz否则我们就把这个最小距离的点标记为true紧接着我们对于长度进行记录累加然后我们对于这个最近点的一些连接点进行遍历更新其一些点的最小距离。这整一个过程遍历n遍就行了。(等我们代码写出来会发现它的代码逻辑和Dijkstra十分相似)#includebits/stdc.husingnamespacestd;constintN5010;constintINF0x3f3f3f3f;intn,m;intg[N][N];intdist[N];boolst[N];intans0;voidprime(){memset(dist,0x3f,sizeofdist);dist[1]0;ans0;for(inti0;in;i){intt-1;for(intj1;jn;j)if(!st[j](t-1||dist[t]dist[j]))tj;if(t-1||dist[t]INF){ans-1;return;}st[t]true;if(i)ansdist[t];for(intj1;jn;j){if(!st[j]g[t][j]dist[j])dist[j]g[t][j];}}}intmain(){cinnm;memset(g,0x3f,sizeofg);for(inti0;im;i){inta,b,c;cinabc;g[a][b]min(g[a][b],c);g[b][a]min(g[b][a],c);}prime();if(ans-1)coutorzendl;elsecoutansendl;}这个过程和Dijkstra基本一致但是由于一个是最短路径一个是最小生成树所以这里写法会有点不同但是我们理解起来就很好了。克鲁斯卡尔算法这个算法可以处理边稀疏问题并且时将复杂度上也比Prim好一个log级别它的思路和Prim不同的是那个是找从一个集合出发的最短路径而这个算法我们找的是整局的最短路径只要不会造成重复和成环最终我们只要达到n个点选择n-1个点就行了。堆还有一点区别就是Prim算法一般都是给你一个点进行选择线段来生成最小树而克鲁斯卡尔是不给你点让你自己来选选择一个点所以还有这点差别并运用了并查集的知识。首席按选择最短边这个过程我们就需要进行结构体排序然后我们进行遍历结构体的一个一个点进行并查集来判断这个点是否已经在一个集合里面要是不在我们就要它并累加权值最后我们输出累加权值就行了。其一个很标准的题目挖沟它就是一个很标准的克鲁斯卡尔板子题目先定义一个结构体然后输入之后我们进行排序之后先初始化所有点的跟是自己然后进行遍历所有边对于边的两个点我们看看他们的根是不是一个不是我们就选然后把他们连接起来(连城一个根)然后累加权值如果选了n-1个边我们就提前结束(剪枝)最后输出权值和就行了。#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN100005;intn,m;intp[N];structnode{intu,v,w;};vectornodeg;boolcmp(node a,node b){returna.wb.w;}intfind(intx){if(p[x]!x)p[x]find(p[x]);returnp[x];}signedmain(){cinnm;for(inti0;im;i){intu,v,w;cinuvw;g.push_back({u,v,w});}sort(g.begin(),g.end(),cmp);for(inti1;in;i)p[i]i;intans0;intcnt0;for(inti0;im;i){intug[i].u,vg[i].v,wg[i].w;ufind(u),vfind(v);if(u!v){p[u]v;answ;cnt;if(cntn-1)break;}}coutansendl;}二分图染色法一个十分经典的算法其而二分图可将顶点集合划分为两个独立集且所有边均连接不同集合的图。那么对于不是二分图的即不能构成那么就是会成为奇环由于我们染色法的规则是相邻的颜色不同而如果有一个奇环那么必定会起冲突对于这个图形来讲我们的1点可以用二分图的染色法进行染色但是最终会把1染成1或者2这样就起冲突了所以它就够不成二分图那么对于染色判别我们就也知道了。【模板】二分图结构Ⅰ-A ‖ 染色判定DFS_牛客题霸_牛客网这里有一道很经典的用染色法判断二分图模型那么就根据之前所说染色方法判断是不是二分图。首先就是建图然后定义一个color数组来存每一个点的颜色然后我们遍历n个点来判断它们的每个颜色是不是空的要是空的我们就判断它的分支有没有奇环来一个find的bool函数那么这么find函数怎么判断呢首先颜色我们先给它染上然后遍历它的所有点如果它的点被染上颜色并且和它颜色一样那么肯定是奇环直接退出false要是没染色在判断它的分支是不是奇环是就直接退出false最后判断玩所以就退出为true。这个过程的思路就是递归然后一层一层进一层一层出一层一层判断来实现。#includebits/stdc.husingnamespacestd;constintN300005;vectorintg[N];intcolor[N];intn,m;boolfind(intx,intcnt){color[x]cnt;for(intv:g[x]){if(color[v]0){if(!find(v,3-cnt))returnfalse;}elseif(color[v]cnt)returnfalse;}returntrue;}intmain(){cinnm;for(inti1;im;i){intu,v;cinuv;g[u].push_back(v);g[v].push_back(u);}for(inti1;in;i){if(color[i]0){if(!find(i,1)){coutNOendl;return0;}}}coutYESendl;return0;}匈牙利算法这个算法就是在我们同个染色法进行分组之后我们来进行匹配问题的过程。P3386 【模板】二分图最大匹配 - 洛谷这里的一道模板题是在二分图构建完成后的匹配问题。我们思路就是建图然后遍历每一个点看看有没有适合的匹配有就累加最后输出数量那么这个判断适合的过程怎么办呢我们再定义一个判断函数对于这个函数而言我们遍历这个点的所有连接点如果它的连接点被判断过直接结束这次循环然后就是判断这个点是否已经被连接没有被连接或者已经被链接但是我们能通过find函数再找到一个能和它匹配的那么这个点就可以被我们判断进来的这个点所连接。整个过程还是运用了递归思想就是说如果你的心上人已经梅花有主了但是她的另一半还有暗恋者那么我们就看看他的”暗恋者“是不是无主之人如果是就直接匹配如果不是那么接着递归判断她的心上人是不是还有暗恋着这样最终我们就可以达到尽可能多的所有人都有匹配对。#includebits/stdc.husingnamespacestd;constintN510;vectorintg[N];intmatch[N];boolst[N];intn,m,e;boolfind(intx){for(intv:g[x]){if(st[v])continue;st[v]true;if(match[v]0||find(match[v])){match[v]x;returntrue;}}returnfalse;}intmain(){cinnme;for(inti1;ie;i){intu,v;cinuv;g[u].push_back(v);}intres0;for(inti1;in;i){memset(st,false,sizeofst);if(find(i))res;}coutresendl;return0;}学完这么多的知识可以试着做一些图论相关题了现在我们看到之后不至于一点思路都没有了。这些内容虽然不多但是更多的是理解本质如果真的理解了那么其实也可以一句不说自在理解。