1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int u,v,w;
}e[250005];
int A,B,cnt,tot=1,ans,f[505];
bool cmp(node x,node y){
return x.w<y.w;
}
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void Update(int a,int b){
int x=find(a);
int y=find(b);
if(x!=y) f[x]=y;
return;
}
void addEdge(int a,int b,int c){
cnt++;
e[cnt].u=a;
e[cnt].v=b;
e[cnt].w=c;
return;
}
void kruskal(){
int i=1;
while (i<=cnt&&tot<=B){
if (find(e[i].u)!=find(e[i].v)){
tot++;
ans+=e[i].w;
Update(e[i].u,e[i].v);
}
i++;
}
return;
}
int main(){
scanf("%d%d",&A,&B);
for(int i=1;i<=B;i++)
for(int j=1;j<=B;j++){
int w;
scanf("%d",&w);
if(i<j&&w!=0) addEdge(i,j,w);
}
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);
kruskal();
printf("%d\n",ans);
return 0;
}
|