广州工商学院官网_宣传片拍摄清单_国产免费crm系统有哪些在线_游戏推广怎么做引流

最小生成树入门题，这里我采用prim算法来解决

1、条件准备

ifintree数组标记是否访问过
n,m为结点数量和输入边数量
graph数组存图
N是定义的一个最大值常量

 #include <iostream>#include<vector>#include<string.h>using namespace std;#define endl '\n'int ifintree[1005];int n,m;int graph[1005][1005];const int N=0x01010101;

2、主函数

输入数据存图
这里初始化graph数组的每个字节为1，那么每一个元素值就为N
然后调用prim函数

  int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>m;memset(graph,1,sizeof(graph));while(m--){int a,b,v;cin>>a>>b>>v;graph[a][b]=v;graph[b][a]=v;}prim();return 0;}

3、prim函数

首先定义mindist数组，每个元素值为N，含义为到该生成树上结点的最小值。
然后遍历n-1遍，生成n-1条边，minval为到该生成树的最短距离，cur为该节点标号，第一次进入for循环一定会使得cur为1，最后输出也不用考虑mindist[1]即可算n-1条边
将该节点加入生成树中然后遍历每个结点，更新该结点到生成树上结点的最短距离
最后循环判断mindist数组，如果有值仍为N则没走到该结点，输出-1，否则加到answer上最后输出

void prim()
{vector<int> mindist(1005,N);for(int i=1;i<n;i++){int minval=N+1;int cur=-1;for(int j=1;j<=n;j++)if(!ifintree[j]&&mindist[j]<minval){minval=mindist[j];cur=j;}ifintree[cur]=1;for(int j=1;j<=n;j++){if(!ifintree[j]&&graph[cur][j]<mindist[j])mindist[j]=graph[cur][j];}}int answer=0; for(int i=2;i<=n;i++){ if(mindist[i]==N){cout<<"-1";return;}answer+=mindist[i];}cout<<answer;
}

4、总结

这道题是最小生成树的模板题，较为简单
完整代码如下

  #include <iostream>#include<vector>#include<string.h>using namespace std;#define endl '\n'int ifintree[1005];int n,m;int graph[1005][1005];const int N=0x01010101;void prim()
{vector<int> mindist(1005,N);for(int i=1;i<n;i++){int minval=N+1;int cur=-1;for(int j=1;j<=n;j++)if(!ifintree[j]&&mindist[j]<minval){minval=mindist[j];cur=j;}ifintree[cur]=1;for(int j=1;j<=n;j++){if(!ifintree[j]&&graph[cur][j]<mindist[j])mindist[j]=graph[cur][j];}}int answer=0; for(int i=2;i<=n;i++){ if(mindist[i]==N){cout<<"-1";return;}answer+=mindist[i];}cout<<answer;
}int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>m;memset(graph,1,sizeof(graph));while(m--){int a,b,v;cin>>a>>b>>v;graph[a][b]=v;graph[b][a]=v;}prim();return 0;}