poj 2395 Out of Hay （最小生成树的最大边）

求最小生成树的最大边，一定要注意INF的值，不能太小，因为太小WRong了一次，后来看结题报告才发现！！

[html]
#include"stdio.h" 
#include"string.h" 
#define INF 0x7fffffff//不能过小！！ 
int map[2001][2001],f[2001],mark[2001],n,m; 
void prime() 
{ 
    int i,j,k,min,max; 
    memset(mark,0,sizeof(mark)); 
    for(i=1;i<=n;i++) 
        f[i]=map[1][i]; 
    f[1]=0;mark[1]=1; 
    max=-1; 
    for(i=1;i<n;i++) 
    { 
        min=INF; 
        for(j=1;j<=n;j++) 
        { 
            if(!mark[j]&&f[j]<min) 
            { 
                min=f[j];k=j; 
            } 
        } 
        mark[k]=1; 
        max=max>min?max:min; 
        for(j=1;j<=n;j++) 
        { 
            if(f[j]>map[k][j]&&!mark[j]) 
                f[j]=map[k][j]; 
        } 
    } 
    printf("%d\n",max); 
} 
int main() 
{ 
    int i,j,a,b,c; 
    while(scanf("%d%d",&n,&m)!=-1) 
    { 
        memset(map,76,sizeof(map)); 
        for(i=0;i<m;i++) 
        { 
            scanf("%d%d%d",&a,&b,&c); 
            if(map[a][b]>c)map[a][b]=c; 
            if(map[b][a]>c)map[b][a]=c; 
        } 
        prime(); 
    } 
    return 0; 
} 

补充：软件开发 , C++ ,

上一个：objective-c 自定义 NSDictionary 键类的注意事项
下一个：ZOJ 3631 Watashi's BG