求助

P3366 【模板】最小生成树

txp2024 @ 2024-03-16 12:40:32

1号2号测试点下载测试过后输出结果一致,样例测试也一致,但是就是不给过。爆RE。求改代码。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

struct Edge{//存信息
    ll to,right;// to
};

vector< vector< ll > > v;
vector< bool > vis;
vector< Edge > ve;
ll N,M,ans=0,to; // N个点 M个边

bool cmp( Edge a, Edge b)
{
    return a.right > b.right;
}

void DFS(ll n,ll m)
{
    if(n == N)//如果已经联通的边包含全部边
    {
        printf("%lld",ans);
        exit(EXIT_SUCCESS);
        return;
    }
    for (ll i = 0; i < N; i++)//寻找所以当前寻找点联通的边
    {
        if(v[m][i] != -1 && !vis[i])//如果这个点可以被当前寻找点到达。且没有被走过
        {
            Edge EDGE;              //添加到ve备用
            EDGE.right = v[m][i];   
            EDGE.to = i;            
            ve.push_back(EDGE);     
        }
    }
    for (ll i = ve.size()-1; i >= 0; i--) //去除已经没有实际意义的路径存储
    {
        if(vis[ ve[i].to ])
        {
            ve.erase(ve.begin() + i); //删掉它
        }
    }
    sort(ve.begin(),ve.end(),cmp);  //排序以寻找路权最小的,和当前树连接的点

    if (ve.size()>0)//如果可以有点被选择
    {
        ans += ve[ve.size()-1].right;  //选择它加上他的路权
        vis[ ve[ve.size()-1].to ] = true; //将他标记为 "已经连接"
        to = ve[ve.size()-1].to;
        ve.erase( ve.end() );   //删除
        DFS(n+1, to );  //继续
    }
    else
    {
        printf("orz");
        exit(EXIT_SUCCESS);
    }
    return;
}

int main()
{
    //freopen("D:\\code\\C++\\SHU_RU.in", "r", stdin);
    //freopen("D:\\code\\C++\\SHU_CHU.out", "w", stdout);
    scanf("%lld%lld",&N,&M);
    vis.resize(N,false);
    v.resize(N);
    for (ll i = 0; i < N; i++)
    {
        v[i].resize(N,-1);
    }

    for (ll i = 0; i < M; i++)
    {
        {
            ll A,B,Z;
            cin>>A>>B>>Z;
            if(A!=B)
            {
                if(v[--A][--B] == -1 || v[A][B] > Z)
                {
                    v[A][B] = Z;
                    v[B][A] = Z;
                }
            }
        }
    }
    vis[0] = true;
    DFS(1,0);
    return 0;
}

by txp2024 @ 2024-03-16 12:42:42

补一句,1号2号测试点本地测试过了,提交测试RE


|