什么是最小生成樹？

????????在一給定的無向圖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;
}