忘了具体什么时候写的,应该是 2023.8 初
这算是个算法复习,因为我太菜了以前学的都不会了。
最小生成树
Prim
本质就是一个点去更新它的所有边连接的点,因为最小生成树的本质是形成一个 \(n-1\) 条边的联通图,所以我们需要达成两个条件:
- 所有点都联通
- 每个点选的边尽可能小
所以我们就可以考虑贪心,我们假设 \(1\) 号节点是开始位置,最终所有的点都要和它联通,我们令 \(dis_i\) 表示 \(i\) 点被联通所需要的最小代价,然后从 \(dis\) 最小的 \(i\) 开始更新(一开始是从 \(1\) 开始,\(dis_1=0\)),然后把每个 \(dis\) 更新并且加到优先队列里(优先队列维护最小 \(dis\))。
是不是很像 \(dijkstra\),其实用到的贪心思路都差不多,就是用每次用当前得到的最优解去更新其他点的答案,最后得到全局的答案。
所以我们就得到了一个跟 \(Dijkstra\) 长得非常像并且复杂度比较稳定在(\(O(n\log n)\))的代码:
\(Code\)
//Prim O(n log n)
typedef pair<int,int> PII;
int n,m,dis[5002],ans,cnt;
bool vis[5002];
vector<PII>f[5002];
priority_queue<PII>Q;
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
f[u].push_back({v,w});
f[v].push_back({u,w});
}
memset(dis,0x3f,sizeof(dis));
Q.push({(dis[1]=0),1});
while(!Q.empty()&&cnt<n){
int x=Q.top().second;Q.pop();
if(vis[x])continue;
vis[x]=1;
cnt++,ans+=dis[x];
for(PII PI:f[x]){
int y=PI.first,w=PI.second;
if(dis[y]>w)dis[y]=w,Q.push({-w,y});
}
}
if(cnt!=n)puts("orz");
else printf("%d",ans);
}
Kruskal
本质也是和 \(Prim\) 一样,找尽可能最小边,我们发现最小的边如果可以连接两个不同的连通块,那么一定会被选。假设我们不选,此时我们用另外一条比较大的边连接这两个连通块,答案肯定不是最优的。
当然加边之前还得确认两个点不在一个连通块内,用并查集维护即可。
极限最优复杂度 \(O(m\log m\alpha(n))\)。(O(\(\alpha(n)\)) 是并查集复杂度)
按理来说应该不会比我的 \(Prim\) 快,但是可能是有小优化,居然跑飞快。
\(Code\)
//Kruskal O(m\log m \log n)
struct edge{
int u,v,w;
inline bool operator <(const edge &o)const{
return w>o.w;
}
};
int n,m,fa[5002],ans,cnt=1;
priority_queue<edge>Q;
inline int find(int x){return (x==fa[x]?x:(fa[x]=find(fa[x])));}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
Q.push({u,v,w});
}
while(!Q.empty()&&cnt<n){
int u=Q.top().u,v=Q.top().v,w=Q.top().w;
Q.pop();
if(find(u)==find(v))continue;
cnt++,ans+=w;
fa[find(u)]=find(v);
}
if(cnt!=n)puts("orz");
else printf("%d",ans);
}
标签:5002,Prim,log,int,最小,生成,dis
From: https://www.cnblogs.com/NBest/p/17745588.html