唐尧文化 网站建设工作总结,淘宝网站怎么做链接地址,电脑端网站和手机网站区别,北辰做网站首先#xff0c;什么是最小生成树#xff1f;
他就是无向图G中的所有生成树中树枝权值总和最小的。
如何求#xff1f;
我们不妨采用以下的贪心策略#xff1a;
Prim算法#xff08;复杂度#xff1a;#xff08;nm)logm)#xff1a;
我们对于把上述的点看成两个集…首先什么是最小生成树
他就是无向图G中的所有生成树中树枝权值总和最小的。
如何求
我们不妨采用以下的贪心策略
Prim算法复杂度nm)logm)
我们对于把上述的点看成两个集合一个是确定了最小生成树的点一个还没有确定我们只要不断把距离已经确定的集合的最短的边添加进去即可。假如我们加的距离不是最小的那么当我们假设未确定的点已经构成了他们点的最小生成树那么我们此时用距离最小的去添加他们肯定更优。我们对于那先未确定的点的集合不管用什么边去联系他们任何一个点都不会影响他们以后的最小生成树的形状这也是贪心当前最优解可以推出全局最优解的保证
来道模板题 因为传递消息至少连n-1条边又要距离min相当于求最小生成树下面是AC代码我们可以优化一下对于还未拿出的边若有一个比他长的则不放入队列
#includebits/stdc.h
using namespace std;
int n,m,head[100010],a,b,v,cnt,sum;
struct node{int len,dian,next;
}edge[1000005];
void addedge(int x,int y,int v){edge[cnt].lenv;edge[cnt].diany;edge[cnt].nexthead[x];head[x]cnt;
}
int dis[100010];
struct ty{int bian,name;bool operator(const ty a) const{return biana.bian;}
};
bool vis[1000001];
priority_queuety q;
int prim(){q.push({0,1});while(!q.empty()){ty ckq.top();q.pop();if(vis[ck.name]1) continue;vis[ck.name]1;sumck.bian;for(int ihead[ck.name];i!-1;iedge[i].next){if(vis[edge[i].dian]1) continue;if(dis[edge[i].dian]edge[i].len) continue;dis[edge[i].dian]edge[i].len;q.push({edge[i].len,edge[i].dian});}}return sum;
}
int main(){memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));cinnm;for(int i1;im;i){scanf(%d%d%d,a,b,v);addedge(a,b,v);addedge(b,a,v);}coutprim();
}
Kruskal算法(复杂度mlogm)
还是采取贪心策略只不过这次是直接选所有边下的最短边若他们连起来还是树就连起来反之舍弃用并查集维护即可。
首先我们注意到如果每一次都可以选min的n-1条边就是最优的情况。
但是在实际上可能边会在同一个并查集中说明这条边可以发挥构成树的作用当时已经存在一点他的作用是一样的但是它的距离更小因此更优。换句话说我们就是在选n-1个在构建生成树的发挥不同作用的边而之所以要放弃是因为功能的重叠。
综上这样选取的策略最优。
下面给出AC代码
#includebits/stdc.h
using namespace std;
int n,m,fa[100010],a,b,v,cnt,sum;
struct node{int len,x,y;
}edge[1000005];
bool cmp(node a,node b){return a.lenb.len;
}
int find(int x){if(fa[x]x) return x;else return fa[x]find(fa[x]);
}
void merge(int x,int y){fa[find(x)]find(y);
}
int main(){cinnm;for(int i1;in;i) fa[i]i;for(int i1;im;i){scanf(%d%d%d,a,b,v);edge[cnt].xa;edge[cnt].yb;edge[cnt].lenv;}sort(edge1,edge1m,cmp);for(int i1;im;i){int xxfind(edge[i].x);int yyfind(edge[i].y);if(xxyy) continue;sumedge[i].len;merge(xx,yy);}coutsum;
}
