二维平面上有 \(n\) 个点, 每两个点间如果连边, 那么权值定义为它们距离的平方. 只允许连接权值 \(\geq C\) 的边, 求最小生成树.\(n \leq 2000\)
Solution
难度: L1
暴力连边然后跑 MST (应该能卡过去吧)
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 2000005;
- int n,fa[2005],ans,c,ind,x[2005],y[2005];
- struct edge {
- int u,v,w;
- bool operator <(const edge &b) const {
- return w < b.w;
- }
- } e[N];
- int find(int p) {
- return fa[p]==p?p:fa[p]=find(fa[p]);
- }
- void merge(int p,int q) {
- p=find(p); q=find(q);
- if(p!=q) fa[p]=q;
- }
- signed main() {
- iOS::sync_with_stdio(false);
- cin>>n>>c;
- for(int i=1;i<=n;i++) {
- cin>>x[i]>>y[i];
- }
- for(int i=1;i<=n;i++) {
- for(int j=1;j<i;j++) {
- int tmp = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
- if(tmp>=c) e[++ind]={i,j,tmp};
- }
- }
- for(int i=1;i<=n;i++) fa[i]=i;
- sort(e+1,e+ind+1);
- for(int i=1;i<=ind;i++) {
- edge ed = e[i];
- if(find(ed.u)!=find(ed.v)) {
- merge(ed.u,ed.v);
- ans+=ed.w;
- }
- }
- for(int i=2;i<=n;i++) if(find(i)!=find(1)) {
- cout<<-1;
- return 0;
- }
- cout<<ans;
- }
[USACO14MAR] Watering the Fields S - 最小生成树
来源: http://www.bubuko.com/infodetail-3461280.html