(最小生成树)HDU 1233 还是畅通工程

查看原题

题意

最小生成树

思路

Prim 我套了之前的模板

代码

#include <iostream> using namespace std; int main(int argc, char *argv[]) { int n,a,b,x; while(cin>>n&&n){ int num[101][101],visted[101]={0},lowest[101]={999999}; for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ num[i][j]=999999; } } for(int i=0;i<n*(n-1)/2;i++){ cin>>a>>b>>x; if(x<num[a][b]){ num[a][b]=num[b][a]=x; } } int step=1,temp,sum=0,i,j; for(i=1;i<=n;i++){ lowest[i]=num[step][i]; } visted[step]=1; for(i=1;i<n;i++){ temp=999999; for(j=1;j<=n;j++){ if(!visted[j]&&lowest[j]<temp){ temp=lowest[j]; step=j; } } visted[step]=1; sum+=temp; for(int k=1;k<=n;k++){ if(!visted[k]&&num[step][k]<lowest[k]){ lowest[k]=num[step][k]; } } } cout<<sum<<endl; } return 0; }