1.最小生成树与最短路的区别
最小生成树:把连通的图的所有顶点连起来路径之和最小的问题,即生成树总权值之和最小。
最短路:把两点之间路径最短。
最短路只是需要将两个点连起来,其路径并不一定经过所用点,而最小生成树要连接每一个点
eg: 下图中,A->D的最短路= AC+CD ; 最小生成树 = AC+CD+AB
2.prim 与 dijkstra 思路区别
dijkstra:把所有点到 源点 距离dis设成∞
,每次找到dis最小的点 确定下来(加入到路径中),并用该点距离更新所有点到源点距离 dis[i]=min(dis[i],w+a[t][i]);
即:用源点扩展,每次确定距离最近的点,直到终点!!
prim: : 把所有点到 集合 的距离dis设成∞
,每次找到dis最小的点 确定下来(加入到集合中),并用该点距离更新所有点到集合距离 dis[i]=min(dis[i],a[t][i]);
即:随意找一个起点,每次确定到集合最近的点,直到所有点都确定完!!
由上面的思路区别,不难看出唯一区别就是,dijkstra
更新的是到源点的距离,prim
更新的是到集合的距离。
3.prim 与 dijkstra 代码区别
由上面可知 dijkstra
和prim
的唯一区别,那是不是只需要将dijkstra
代码中的 dis
更改成到集合的距离就可以了?像下面这样:
试过之后发现并不能AC。
其实思路并没错,只是prim 是到集合的距离,所以后面的点可能会更新前面已经确定点的距离,不像dijstra
是到源点的距离后面的距离定这会更大,不会更新前面的dis
eg: q为队列中放内容
综上所述:只需要将已经确定的点的dis不在被改变即可:
void bfs()
{
priority_queue<PII,vector<PII>,greater<PII>> q;
memset(res,0x3f,sizeof res);
res[1]=0;
q.push({0,1});
while(q.size())
{
auto t=q.top();
q.pop();
if(st[t.second]) continue;
st[t.second]=true;
for(int i=h[t.second];i!=-1;i=ne[i])
{
int k=e[i];
if(res[k]>w[i]&&!st[k]) //这里加个标记
{
res[k]=w[i];
q.push({res[k],k});
}
}
}
}
4.关于prim细节
- y总的代码在统计总和时是在 确定每个点后加上res+=dis, 并不能等到最后在遍历 求dis的总和原因如上第三个标题
- prim和dijkstra 都是差不多都是基于 bfs 思路
- 具体代码: 下面存边用的时邻接表存的,主要是为了更好区别dijstra,用邻接矩阵松弛操作直接for循环遍历每个点即可。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
typedef pair<LL ,LL >PII;
const int N=1e6;
LL n,m,resmax;
LL e[N],ne[N],w[N],idx=0,h[N];
LL res[N];
bool st[N];
void add(int a,int b,LL ww)
{
e[idx]=b,ne[idx]=h[a],w[idx]=ww,h[a]=idx++;
}
void bfs()
{
priority_queue<PII,vector<PII>,greater<PII>> q;
memset(res,0x3f,sizeof res);
res[1]=0;
q.push({0,1});
while(q.size())
{
auto t=q.top();
q.pop();
if(st[t.second]) continue;
st[t.second]=true;
for(int i=h[t.second];i!=-1;i=ne[i])
{
int k=e[i];
if(res[k]>w[i]&&!st[k])
{
res[k]=w[i];
q.push({res[k],k});
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++)
{
LL a,b,ww;
cin>>a>>b>>ww;
add(a,b,ww);
add(b,a,ww);
}
bfs();
for(int i=2;i<=n;i++)
{
resmax=resmax+res[i];
if(res[i]>0x3f3f3f3f)
{
cout<<"impossible";
return 0;
}
}
cout<<resmax;
}
也可以直接在确定每个点的时候累计长度,不过需要一个额外的变量cnt来计算生成树的边数,如果边数cnt<n-1,就说明图不连通。
是不是说反了,如果prim会更新前面的dist那不是应该不加标记? 而且加不加应该无所谓不,prim的dist确认后就不会再用到了,我把标记加上或去掉都能ac
上面序号3的左边图片的dijkstra在松弛的时候代码不应该是if(dis[k]>t.first+w[i])吗?
这个写的真的很细节。谢谢楼主
哈哈哈哈哈
狠狠地学了一波
哈哈哈哈