hdoj 1863 畅通工程 最小生成树---prime算法
#include <iostream>
#include <cstring>
using namespace std;
const int inf=0xffffff;
int weight[105][105],n,m;
int prime()
{
int sum=0;
int pre[105];
int dis[105];
bool visit[105];
memset(visit,0,sizeof(visit));
for(int i=1;i<=m;i++)
{
dis[i]=weight[1][i];
pre[i]=1;
}
visit[1]=1;
for(int i=1;i<m;i++)
{
int minimum=inf;
int index=-1;
for(int j=1;j<=m;j++)
{
if(!visit[j] &&dis[j]<minimum){
minimum=dis[j];
index=j;
}
}
if(index==-1)return inf;
visit[index]=1;
sum+=weight[pre[index]][index];
for(int j=1;j<=m;j++)
{
if(!visit[j]&& dis[j]>weight[index][j])
{
dis[j]=weight[index][j];
pre[j]=index;
}
}
}
return sum;
}
int main()
{
while(cin>>n>>m)
{
if(n==0)break;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
weight[i][j]=inf;
for(int i=0;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
weight[x][y]=z;
weight[y][x]=z;
}
int ans=prime();
if(ans==inf){cout<<"?"<<endl;continue;}
cout<<ans<<endl;
}
}
#include <iostream>
#include <cstring>
using namespace std;
const int inf=0xffffff;
int weight[105][105],n,m;
int prime()
{
int sum=0;
int pre[105];
int dis[105];
bool visit[105];
memset(visit,0,sizeof(visit));
for(int i=1;i<=m;i++)
{
dis[i]=weight[1][i];
pre[i]=1;
}
visit[1]=1;
for(int i=1;i<m;i++)
{
int minimum=inf;
int index=-1;
for(int j=1;j<=m;j++)
{
if(!visit[j] &&dis[j]<minimum){
minimum=dis[j];
index=j;
}
}
if(index==-1)return inf;
visit[index]=1;
sum+=weight[pre[index]][index];
for(int j=1;j<=m;j++)
{
if(!visit[j]&& dis[j]>weight[index][j])
{
dis[j]=weight[index][j];
pre[j]=index;
}
}
}
return sum;
}
int main()
{
while(cin>>n>>m)
{
if(n==0)break;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
weight[i][j]=inf;
for(int i=0;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
weight[x][y]=z;
weight[y][x]=z;
}
int ans=prime();
if(ans==inf){cout<<"?"<<endl;continue;}
cout<<ans<<endl;
}
}
补充：软件开发 , C++ ,
