1 条题解
-
0
用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
- 上传者