山西建设厅网站查不了,域名频道注册域名,seo和sem推广,为国外客户做网站建设这题太水了吧#xff0c;不知道怎么蓝的#xff0c;蒟蒻只写了十五分钟就一次AC了…… 但是挺有意思#xff0c;就发篇题解吧qwq emmm……最小生成树#xff08;贪心#xff09;#xff0c;就没别的了…… 要明确#xff1a; 一开始可以把每个点都看成一个部落#xff… 这题太水了吧不知道怎么蓝的蒟蒻只写了十五分钟就一次AC了…… 但是挺有意思就发篇题解吧qwq emmm……最小生成树贪心就没别的了…… 要明确 一开始可以把每个点都看成一个部落那么每一次连一条不相通的边时就相当于合并了两个部落。 那么当剩下k个部落的时候找下一条边即可。 有一个要注意 就是当已经找完所有边时不能直接输出第i1条而是要继续找直到找到下一条合法边原因很简单就不解释了…… 代码代码 #includecstdio
#includealgorithm
#includeiostream
#includecmath
using namespace std;
#define maxn 1000005
//#define int double
int n,k,cnt;
int nx[1005],ny[1005],par[maxn];
struct node
{int from,to;double w;
} q[maxn];
bool cmp(node a,node b)
{return a.wb.w;
}
double use(int x,int y,int xx,int yy)
{return sqrt( pow(x-xx,2)pow(y-yy,2) );
}
void add(int x,int y,double e)
{q[cnt].toy;q[cnt].fromx;q[cnt].we;
}
int find(int x)
{return xpar[x] ? x : par[x]find(par[x]);
}
void merge(int x,int y)
{par[find(y)]find(x);
}
void kruskal()
{for(int i1;icnt;i){int nowxq[i].from,nowyq[i].to;if(find(nowx)find(nowy))continue;merge(nowx,nowy);n--;if(nk-1){printf(%.2lf,q[i].w);break;}}
}
main()
{scanf(%d%d,n,k);for(int i1;in;i)par[i]i;for(int i1;in;i)scanf(%d%d,nx[i],ny[i]);for(int i1;in;i)for(int j1;ji;j){double euse(nx[i],ny[i],nx[j],ny[j]);add(i,j,e);add(j,i,e);}sort(q1,qcnt1,cmp);kruskal();return 0;
} 这么简单的题要不去直接AC吧~转载于:https://www.cnblogs.com/popo-black-cat/p/10067917.html
