prim最小生成树+最大生成树【C++】板子题

什么是最小生成树？

        在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此的边权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。最小生成树其实是最小权重生成树的简称。（简而言之就是把一个图变成一棵树，并且树中的边权和最小）

抓概念的话下面这个人就解释的很详细

最小生成树——Prim算法（详细图解）_最小生成树prim算法-CSDN博客

 标准的Prim模板--最小生成树

const int MAXN = 1000,INF = 0x3f3f3f3f;//定义一个INF表示无穷大。
int g[MAXN][MAXN],dist[MAXN],n,m,res;
//我们用g[][]数组存储这个图，dist[]储存到集合S的距离，res保存结果。
bool book[MAXN];//用book数组记录某个点是否加入到集合S中。int main()
{cin>>n>>m;//读入这个图的点数n和边数mfor(int i = 1 ; i<= n ;i++){for(int j = 1; j <= n ;j++){g[i][j] = INF;//初始化任意两个点之间的距离为正无穷（表示这两个点之间没有边）}dist[i] = INF;//初始化所有点到集合S的距离都是正无穷}for(int i = 1; i <= m ; i++){int a,b,w;cin>>a>>b>>w;//读入a，b两个点之间的边g[a][b] = g[b][a] = w;//由于是无向边，我们对g[a][b]和g[b][a]都要赋值}prim();//调用prim函数if(res==INF)//如果res的值是正无穷，表示不能该图不能转化成一棵树，输出orzcout<<"orz";elsecout<<res;//否则就输出结果resreturn 0;
}void prim()
{dist[1] = 0;//把点1加入集合S，点1在集合S中，将它到集合的距离初始化为0book[1] = true;//表示点1已经加入到了S集合中for(int i = 2 ; i <= n ;i++)dist[i] = min(dist[i],g[1][i]);//用点1去更新dist[]for(int i = 2 ; i <= n ; i++){int temp = INF;//初始化距离int t = -1;//接下来去寻找离集合S最近的点加入到集合中，用t记录这个点的下标。for(int j = 2 ; j <= n; j++){if(!book[j]&&dist[j]<temp)//如果这个点没有加入集合S，而且这个点到集合的距离小于temp就将下标赋给t{temp = dist[j];//更新集合V到集合S的最小值t = j;//把点赋给t}}if(t==-1){res = INF ; return ;}//如果t==-1，意味着在集合V找不到边连向集合S，生成树构建失败，将res赋值正无穷表示构建失败，结束函数book[t] = true;//如果找到了这个点，就把它加入集合Sres+=dist[t];//加上这个点到集合S的距离for(int j = 2 ; j <= n ; j++)dist[j] = min(dist[j],g[t][j]);//用新加入的点更新dist[]}
}

改良版的最大生成树

注意字符串可旋转不可翻转

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 210,M = 51;
vector<string>s(210);
int n,m;
int dist[N],ans,g[N][N],f[N][N],st[N];
int cal_lcs(string a,string b){a = " "+ a, b =" "+b;memset(f,0,sizeof f);int cnt = 0;for(int i = 1;i<=2*m;++i){for(int j = 1;j<=2*m;++j){if(a[i] == b[j]) f[i][j] = max(f[i][j],f[i-1][j-1]+1);cnt = max(cnt,f[i][j]);}}return cnt;
}
int main(){cin>>n>>m;//拆环为链，复制一遍字符串串 for(int i = 1; i <= n;++i){cin>>s[i];s[i]+=s[i];}for(int i = 1; i<= n;++i){for(int j = i;j <= n ;++j){if(i==j) g[i][j] = 0;else g[i][j] = g[j][i] = min(cal_lcs(s[i],s[j]),m);//只计算一遍g[i][j] }}//朴素版Prim算法，注意要求最大生成树，都要修改为大于号 for(int i = 1;i <= n; ++i){int t = -1;for(int j = 1;j<=n;++j){if(!st[j]&&(t==-1||dist[j]>dist[t])) t = j;}st[t] = 1;ans += dist[t];for(int j = 1;j<=n;++j){if(!st[j] && dist[j] < g[t][j]) dist[j] = g[t][j];}}cout<<ans<<endl;
}