码风不太好,请各位大佬谅解
by charliegong @ 2019-05-28 23:22:25
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#define MAXN 1000
using namespace std;
int n,m,v;
struct Edge{
int u,v,c;
bool operator < (const Edge t) const{
return t.c>c;
}
}e[1000001];
int tot=0,fa[100001];
int get(int x){
if(fa[x]==x) return x;
else return fa[x]=get(fa[x]);
}
int kruskal(){
sort(e+1,e+1+tot);
int ans=0,cnt=0;
for(int i=1;i<=m;i++) fa[i]=i;
for(int i=1;i<=tot;i++){
int fu=get(e[i].u);
int fv=get(e[i].v);
if(fu==fv) continue;
fa[fu]=fv;
cnt++;
ans+=min(n,e[i].c);
}
return ans;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
cin>>v;
if(v)
{
e[++tot].u=i;
e[tot].v=j;
e[tot].c=v;
}
// g[i][j]=min(g[i][j],n);
}
}
cout<<kruskal() + n<<endl;
return 0;
}
```
@[charliegong](/space/show?uid=95626)
by Strong_Jelly @ 2019-05-29 08:05:57
数组开小了,sort是到tot,大于n的取n,第一个不优惠+n
by Strong_Jelly @ 2019-05-29 08:09:10
@神兵qqq1112非常感谢
by charliegong @ 2019-05-29 10:59:56