企业官网建设流程全解析

图论–最小生成树

本小章节的内容颇多，但是董事很经典的内容，由于主包也是一名实用主义，所以不适用的知识我们也直接不讲了！

我们的最小生成树内容有如下

啊，图上也打对叉了，这个Prim堆优化版本十分不常用，一般都是用克鲁斯卡尔来代替，因为克鲁斯卡尔时间复杂度比它快个常数倍，然后苏里还很好理解。

二分图也是一个很常考，很重要的算法，在这里一并讲解了。

最小生成树：

Prim（朴素版本）

克鲁斯卡尔

二分图

染色法

匈牙利算法

点击上方专辑试试呢！

最小生成树

Prim（朴素版本）

Prim算法是一个很经典的找最小生成树问题，其板子如下

P3366 【模板】最小生成树 - 洛谷

其做法就是先建图这个图论的很多问题都是先建图，之后直接进入Prim函数来运行，那么我们的Prim怎么做呢？首先我们把所有的点都初始化为INF，只有点1的距离是0，那么对于n个点，我们遍历n次，对于每一个点，如果它没有被标记过，并且它如果是找到的第一个没被标记的点，或者这个点比上一个点距离更加近，那么我们就把指针变到j，最后如果没找到或者这个点的距离是正无穷，那么肯定是不符合题意的，直接退出函数输出orz，否则我们就把这个最小距离的点标记为true，紧接着我们对于长度进行记录累加，然后我们对于这个最近点的一些连接点进行遍历，更新其一些点的最小距离。这整一个过程遍历n遍就行了。(等我们代码写出来，会发现，它的代码逻辑和Dijkstra十分相似)

#include<bits/stdc++.h>usingnamespacestd;constintN=5010;constintINF=0x3f3f3f3f;intn,m;intg[N][N];intdist[N];boolst[N];intans=0;voidprime(){memset(dist,0x3f,sizeofdist);dist[1]=0;ans=0;for(inti=0;i<n;i++){intt=-1;for(intj=1;j<=n;j++)if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;if(t==-1||dist[t]==INF){ans=-1;return;}st[t]=true;if(i)ans+=dist[t];for(intj=1;j<=n;j++){if(!st[j]&&g[t][j]<dist[j])dist[j]=g[t][j];}}}intmain(){cin>>n>>m;memset(g,0x3f,sizeofg);for(inti=0;i<m;i++){inta,b,c;cin>>a>>b>>c;g[a][b]=min(g[a][b],c);g[b][a]=min(g[b][a],c);}prime();if(ans==-1)cout<<"orz"<<endl;elsecout<<ans<<endl;}

这个过程和Dijkstra基本一致，但是由于一个是最短路径，一个是最小生成树，所以这里写法会有点不同，但是我们理解起来就很好了。

克鲁斯卡尔算法

这个算法可以处理边稀疏问题，并且时将复杂度上也比Prim好一个log级别，它的思路和Prim不同的是，那个是找从一个集合出发的最短路径，而这个算法我们找的是整局的最短路径，只要不会造成重复和成环，最终我们只要达到n个点选择n-1个点就行了。

堆，还有一点区别就是，Prim算法一般都是给你一个点进行选择线段来生成最小树，而克鲁斯卡尔是不给你点，让你自己来选选择一个点，所以还有这点差别，并运用了并查集的知识。首席按选择最短边这个过程我们就需要进行结构体排序，然后我们进行遍历结构体的一个一个点，进行并查集来判断这个点是否已经在一个集合里面，要是不在，我们就要它并累加权值，最后我们输出累加权值就行了。

其一个很标准的题目：挖沟

它就是一个很标准的克鲁斯卡尔板子题目，先定义一个结构体，然后输入之后我们进行排序，之后先初始化所有点的跟是自己，然后进行遍历所有边，对于边的两个点，我们看看他们的根是不是一个，不是我们就选，然后把他们连接起来(连城一个根)，然后累加权值，如果选了n-1个边我们就提前结束(剪枝)，最后输出权值和就行了。

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=100005;intn,m;intp[N];structnode{intu,v,w;};vector<node>g;boolcmp(node a,node b){returna.w<b.w;}intfind(intx){if(p[x]!=x)p[x]=find(p[x]);returnp[x];}signedmain(){cin>>n>>m;for(inti=0;i<m;i++){intu,v,w;cin>>u>>v>>w;g.push_back({u,v,w});}sort(g.begin(),g.end(),cmp);for(inti=1;i<=n;i++)p[i]=i;intans=0;intcnt=0;for(inti=0;i<m;i++){intu=g[i].u,v=g[i].v,w=g[i].w;u=find(u),v=find(v);if(u!=v){p[u]=v;ans+=w;cnt++;if(cnt==n-1)break;}}cout<<ans<<endl;}

二分图

染色法

一个十分经典的算法，其而二分图可将顶点集合划分为两个独立集，且所有边均连接不同集合的图。

那么对于不是二分图的，即不能构成，那么就是会成为奇环，由于我们染色法的规则是相邻的颜色不同，而如果有一个奇环那么必定会起冲突

对于这个图形来讲，我们的1点可以用二分图的染色法进行染色，但是最终会把1染成1或者2，这样就起冲突了，所以它就够不成二分图，那么对于染色判别我们就也知道了。

【模板】二分图结构Ⅰ-A ‖ 染色判定：DFS_牛客题霸_牛客网

这里有一道很经典的用染色法判断二分图模型，那么就根据之前所说染色方法，判断是不是二分图。

首先就是建图，然后定义一个color数组来存每一个点的颜色，然后我们遍历n个点，来判断它们的每个颜色是不是空的，要是空的我们就判断它的分支有没有奇环，来一个find的bool函数，那么这么find函数怎么判断呢？首先颜色我们先给它染上，然后遍历它的所有点，如果它的点被染上颜色并且和它颜色一样，那么肯定是奇环，直接退出false，要是没染色，在判断它的分支是不是奇环，是就直接退出false，最后判断玩所以，就退出为true。

这个过程的思路就是递归，然后一层一层进，一层一层出，一层一层判断来实现。

#include<bits/stdc++.h>usingnamespacestd;constintN=300005;vector<int>g[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(){cin>>n>>m;for(inti=1;i<=m;i++){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}for(inti=1;i<=n;i++){if(color[i]==0){if(!find(i,1)){cout<<"NO"<<endl;return0;}}}cout<<"YES"<<endl;return0;}

匈牙利算法

这个算法就是在我们同个染色法进行分组之后，我们来进行匹配问题的过程。

P3386 【模板】二分图最大匹配 - 洛谷

这里的一道模板题是在二分图构建完成后的匹配问题。我们思路就是建图，然后遍历每一个点看看有没有适合的匹配，有就累加，最后输出数量，那么这个判断适合的过程怎么办呢？我们再定义一个判断函数，对于这个函数而言，我们遍历这个点的所有连接点，如果它的连接点被判断过直接结束这次循环，然后就是判断这个点是否已经被连接，没有被连接或者已经被链接，但是我们能通过find函数再找到一个能和它匹配的，那么这个点就可以被我们判断进来的这个点所连接。

整个过程还是运用了递归思想，就是说如果你的"心上人"已经梅花有主了，但是她的另一半还有"暗恋者"，那么我们就看看他的”暗恋者“是不是无主之人，如果是就直接匹配，如果不是那么接着递归判断她的"心上人"是不是还有"暗恋着"，这样最终我们就可以达到尽可能多的所有人都有匹配对。

#include<bits/stdc++.h>usingnamespacestd;constintN=510;vector<int>g[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(){cin>>n>>m>>e;for(inti=1;i<=e;i++){intu,v;cin>>u>>v;g[u].push_back(v);}intres=0;for(inti=1;i<=n;i++){memset(st,false,sizeofst);if(find(i))res++;}cout<<res<<endl;return0;}

学完这么多的知识，可以试着做一些图论相关题了，现在我们看到之后不至于一点思路都没有了。这些内容虽然不多，但是更多的是理解本质，如果真的理解了，那么其实也可以一句不说自在理解。