Prim 繁华的都市
安昙
2018-07-16 20:53:53
```cpp
#include<iostream>
#define inf 0x7fffffff
using namespace std;
int g[1000][1000];
int d[1005];
int flag[10005];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
fill(g[i]+1,g[i]+n+1,inf);
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=c;
g[b][a]=c;
}
fill(d+2,d+n+1,inf);
d[1]=0;
int ans=-inf;
for(int i=1;i<=n;i++)
{
int minn=inf,k;
for(int o=1;o<=n;o++)
{
if(minn>d[o]&&!flag[o])
{
minn=d[o];
k=o;
}
}
flag[k]=1;
// cout<<"G::"<<k<<endl;
ans=max(ans,d[k]);
// cout<<"T::"<<ans<<endl;
for(int o=1;o<=n;o++)
{
if(d[o]>g[k][o]&&!flag[o])
d[o]=g[k][o];
}
}
cout<<n-1<<" "<<ans;
}
```