最小生成树 - Prim算法
思路：
采用贪心策略，每次选取连通块外延的最短边和对应的点放入连通块，再更新新的连通块外延的边。连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。
时间复杂度：O( n ^ 2 )，应用于稠密图。
伪代码 / 模板：
int prim(){memset(dist,INF,sizeof dist); //dist[i]表示i节点到连通块的最短路径//st[i]标记i节点是否在连通块内int ans=0;for(int i=0;i<n;i++){int hp=-1;for(int j=1;j<=n;j++){//寻找到连通块最近的点if(!st[j]&&(hp==-1||dist[hp]>dist[j]))hp=j;}if(i&&dist[hp]==INF) //不连通return INF;if(i)ans+=dist[hp];st[hp]=true;for(int j=1;j<=n;j++){//更新外延边dist[j]=min(dist[j],mp[hp][j]);}}return ans; //最小边长和}
模板题：AcWing858. Prim算法求最小生成树
题面：（传送门）
思路：
模板题还需要思路？见前文模板代码注释。
AC代码：
#include<iostream>#include<cstring>using namespace std;const int N=505;const int INF=0x3f3f3f3f;int n,m;int mp[N][N];int dist[N];bool st[N];int prim(){memset(dist,INF,sizeof dist);int ans=0;for(int i=0;i<n;i++){int hp=-1;for(int j=1;j<=n;j++){if(!st[j]&&(hp==-1||dist[hp]>dist[j]))hp=j;}if(i&&dist[hp]==INF)return INF;if(i)ans+=dist[hp];st[hp]=true;for(int j=1;j<=n;j++){dist[j]=min(dist[j],mp[hp][j]);}}return ans;}int main(){//freopen("D:\\in.txt","r",stdin);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)mp[i][j]=1;elsemp[i][j]=INF;}}int u,v,w;for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);mp[u][v]=mp[v][u]=min(mp[u][v],w);}int ans=prim();if(ans==INF)cout<<"impossible"<<endl;elsecout<<ans<<endl;return 0;}
应用题：HDU_7058. Ink on paper
题面：（传送门）
思路：
因为任意两滴墨点只要时间足够都会联通
两个墨点双向奔赴即速度为 1 c m / s 1cm/s 1cm/s
墨点间的距离为 ( x 1 − x 2 ) ∗ ( x 1 − x 2 ) + ( y 1 − y 2 ) ∗ ( y 1 − y 2 ) \sqrt{(x_{1}-x_{2})*(x_{1}-x_{2})+(y_{1}-y_{2})*(y_{1}-y_{2})} (x1−x2)∗(x1−x2)+(y1−y2)∗(y1−y2)
但答案要求输出最短时间的平方
综上，任意两墨点联通的时间的平方即 答案 为 ( x 1 − x 2 ) ∗ ( x 1 − x 2 ) + ( y 1 − y 2 ) ∗ ( y 1 − y 2 ) (x_{1}-x_{2})*(x_{1}-x_{2})+(y_{1}-y_{2})*(y_{1}-y_{2}) (x1−x2)∗(x1−x2)+(y1−y2)∗(y1−y2)
题目就可以转换为：求所有墨点的完全图 的最小生成树 中的最长的边。hu 大喘气
AC代码：
#include<iostream>#include<algorithm>using namespace std;const int N=5005;const long long LLF=9e18;int n;int st[N];long long mp[N][N];long long dist[N];struct Node{long long x,y;}e[N];int main(){//freopen("D:\\in.txt","r",stdin);int T;cin>>T;while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld",&e[i].x,&e[i].y);dist[i]=LLF;st[i]=0;}long long hp;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j){hp=(e[i].x-e[j].x)*(e[i].x-e[j].x)+(e[i].y-e[j].y)*(e[i].y-e[j].y);mp[i][j]=hp;}}}dist[1]=0;long long ans=-1;for(int i=0;i<n;i++){hp=-1;for(int j=1;j<=n;j++)if(!st[j]&&(hp==-1||dist[hp]>dist[j]))hp=j;st[hp]=1;ans=max(ans,dist[hp]);for(int j=1;j<=n;j++)dist[j]=min(dist[j],mp[hp][j]);}cout<<ans<<endl;}return 0;}
