求大佬prim算法为什么爆0

回复帖子

@MKL_SCAR 2018-08-18 15:27 回复

prim算法,10个点,10076ms,T得妥妥的。。。

献上丑陋的代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define repeat(i,KUSSES) for(i=1;i<=KUSSES;++i)
#define PR(...) printf(__VA_ARGS__)
#define LL long long
using namespace std;
LL n,m;
LL g[5001][5001];
LL f[200001];
bool u[200001]={false};
LL ans=-0x7fffff;
LL a,b,l;
LL max(LL a,LL b)
{
    return a>b?a:b;
}
void setmem(LL a[5001][5001],LL s)
{
    int i,j;
    repeat(i,sqrt(sizeof(a)))
    {
        repeat(j,sqrt(sizeof(a)))
        {
            a[i][j]=s;
        }
    }
}
void read(LL &n)
{
    LL x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'||c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    n=x*f;
}
int main()
{
    int i,j;
    setmem(g,0x7fffff);
    read(n);
    read(m);
    repeat(i,m)
    {
        read(a);
        read(b);
        read(l);
        g[a][b]=l;
        g[b][a]=l;
    }
    u[1]=true;
    repeat(i,n)
    {
        int k=0;
        repeat(j,n)
        {
            if(!u[j]&&(f[j]<f[k])){
                k=j;
            }
        }
        u[k]=true;
        repeat(j,n)
        {
            if(!u[j]&&(g[k][j]<f[j])){
                f[j]=g[k][j];
            }
        }
    }
    repeat(i,n)
    {
        ans=max(ans,f[i]);
    }
    PR("%lld\n",&ans);
    return 0;
}

别对我说什么Kruskal,本蒟蒻不会用555555555555555

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。