跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:22:07

    用Prim算法求连接所有计算机的最小生成树,费用和总和使用long long,选点时不以小于合法边权的常量作上限,避免大边权漏选和32位溢出。

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
    
    int n;cin>>n;vector<vector<long long>>a(n,vector<long long>(n));for(auto&row:a)for(auto&x:row)cin>>x;vector<long long>d(n,LLONG_MAX);vector<bool>used(n);d[0]=0;long long answer=0;for(int k=0;k<n;k++){int u=-1;for(int i=0;i<n;i++)if(!used[i]&&(u<0||d[i]<d[u]))u=i;used[u]=true;answer+=d[u];for(int v=0;v<n;v++)if(!used[v])d[v]=min(d[v],a[u][v]);}cout<<answer<<"\n";
    
    return 0;
    }
    
    • 1

    信息

    ID
    4024
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者