kruskal全wa求助! P1194 买礼物
#include<bits/stdc++.h>
using namespace std;
struct edge
{
int u,v,w;
}ed[250005];
int k;
int n,m,ans=0,t[250005],total;
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int find(int u)
{
return t[u]==u ? u : find(t[u]);
}
void init()
{
for(int i=0;i<=n;i++)
{
t[i]=i;
}
}
void init2(int x,int y,int z)
{
k++;
ed[k].u=x;
ed[k].v=y;
ed[k].w=z;
}
int kruskal()
{
init();
sort(ed+1,ed+m+2,cmp);
int xxxx=1;
while(xxxx<=k)
{
int b=find(ed[xxxx].u);
int c=find(ed[xxxx].v);
if(b==c) {xxxx++; continue;}
t[c]=b;
ans+=ed[xxxx].w;
total++;
if(total>=m) break;
xxxx++;
}
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++)
{
int w;
cin>>w;
if(i<j&&w!=0) init2(i,j,w);
}
}
for(int i=1;i<=m;i++)
{
init2(0,i,n);
}
kruskal();
cout<<ans;
return 0;
}