编程实现基于邻接矩阵的最大代价生成树函数;
时间: 2023-06-07 07:10:18 浏览: 50
好的,这是一个编程问题,我可以帮您回答。以下是一个基于邻接矩阵的最大代价生成树函数的示例代码:
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=210;
const int inf=1e18;
struct edge{int to,next,w;}e[maxn*maxn];
int head[maxn],cnt=0;
inline void adde(int x,int y,int z=0){e[++cnt]=(edge){y,head[x],z};head[x]=cnt;}
int n,mat[maxn][maxn],dis[maxn];
bool vis[maxn];
int prim(){
memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis));
dis[1]=0; int res=0;
for(int i=1;i<=n;i++){
int u=0;
for(int j=1;j<=n;j++)
if(!vis[j]&&(u==0||dis[u]>dis[j]))
u=j;
vis[u]=true; res+=dis[u];
for(int j=1;j<=n;j++)
if(!vis[j]) dis[j]=min(dis[j],mat[u][j]);
}
return res;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mat[i][j];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
adde(i,j,mat[i][j]),adde(j,i,mat[i][j]);
cout<<prim()<<endl;
}
```
这里使用的是 prim 算法,将邻接矩阵转化为边表,并进行最大代价生成树的计算。