在吗
by zyh0516_lucky @ 2023-10-16 23:57:28
```cpp
#include <bits/stdc++.h>
using namespace std;
struct s {
int u;
int v;
int w;
} a[1234567];//前向星要开多大开多大
int fa[505];//父数组要开多小开多小
int sum,ans,cnt;
bool cmp(s x,s y) {
return x.w<y.w;
}
void build(int x,int y,int z){
a[++sum].u=x; //这样写虽然没你好看,但更简便
a[sum].v=y;
a[sum].w=z;
}
int find(int x) {
if(fa[x]==x) return x;//不如这样写得更简单些
return fa[x]=find(fa[x]);
}
void unionn(int x,int y) {
int pa=find(x);
int pb=find(y);
if(pa!=pb) {
fa[pa]=pb;
}
}
int main() {
int n,m;
cin>>n>>m;
for(int i=1; i<=m; i++) {
for(int j=1; j<=m; j++) {
int x;
cin>>x;
if(x!=0&&i<j) {
build(i,j,x);
}
}
}
for(int i=1;i<=m;i++){
fa[i]=i;
build(0,i,n);
}
cnt=0;
sort(a+1,a+sum+1,cmp);
for(int i=1;i<=sum;i++){
if(find(a[i].u)!=find(a[i].v)){
ans+=a[i].w;
unionn(a[i].u,a[i].v);
cnt++;
}
if(cnt==m){//我也搞不清,部落划分 这道题也是的,
//考场多试几遍,要不然m-1,要不然m。
//这也是你WA的关键,数组大小是你MLE||REの原因
break;
}
}
cout<<ans<<endl;
return 0;
}
```
看在这份上,给个关不过分吧QWQ
by zyh0516_lucky @ 2023-10-17 00:17:39
@[zl22011909cy](/user/825876) 有两个问题：
1. 数组开小了，边数量的上限应为 $B^2\div 2$，就是 `a[125005]`
2. 别忘了你一开始总得买一个正常价的物品，剩下的物品才能优惠，所以一开始要有 `ans=n`
by hhyz100413 @ 2023-10-17 00:33:03
@[2022zhangyuanhao](/user/746930) 你这不是最纯粹的生成树算法
by Voluminousness @ 2023-10-17 00:35:20
@[hhyz100413](/user/1059609) @[Voluminousness](/user/876418) thx,这也就是循环到m的原因了 吧
by zyh0516_lucky @ 2023-10-17 00:47:33
@[Voluminousness](/user/876418) 这回纯粹了吧哥
```cpp
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <memory>
#include <string>
#include <cstring>
#include <iostream>
#include <queue>
#define ll long long
using namespace std;
int a,b,head[505],cnt,f[505],ans,k;
struct node{
int to,nxt,wei;
}e[1234567];
void addedge(int u,int v,int w){
e[++cnt].to=u;
e[cnt].wei=w;
e[cnt].nxt=v;
//head[u]=cnt;
}
bool cmp(node a,node b){
return a.wei<b.wei;
}
int find(int x){
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
void kruskal(){
int aa,bb;
k=0;
for(int i=1;i<=cnt;i++){
if(k==b-1) return;
aa=find(e[i].to);
bb=find(e[i].nxt);
if(aa!=bb){
f[aa]=bb;
ans+=e[i].wei;
k++;
}
}
return;
}
int main(){
//freopen("binary.in","r",stdin);
//freopen("binary.out","w",stdout);
cin>>a>>b;
int p;
for(int i=1;i<=b;i++)
for(int j=1;j<=b;j++){
cin>>p;
if(i<j&&p)
addedge(i,j,p);
}
for(int i=1;i<=b;i++)
addedge(0,i,a);
for(int i=0;i<=b;i++)
f[i]=i;
sort(e+1,e+cnt+1,cmp);
ans=a;
kruskal();
cout<<ans<<endl;
return 0;
}
```
by zyh0516_lucky @ 2023-10-17 00:50:10
数组是要按pow(B,2)>>1来开的
by zyh0516_lucky @ 2023-10-17 00:51:49
@[2022zhangyuanhao](/user/746930) 对，两种方式是一个意思
by hhyz100413 @ 2023-10-17 16:21:15
@[hhyz100413](/user/1059609) "数组(确实)是",我那句话表示对您的话的肯定
by zyh0516_lucky @ 2023-10-17 18:43:05
感谢关注
by zyh0516_lucky @ 2023-10-18 12:09:17