3 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N = 1010; int mky[N], m, n; int tx[N], ty[N], fa[N]; struct edge{int u, v, w;}; bool operator<(edge a, edge b){return a.w < b.w;} vector<edge> edges; int findfa(int x) {return fa[x] == x ? fa[x] : fa[x] = findfa(fa[x]);} bool merge(int x, int y) { int xfa = findfa(x), yfa = findfa(y); if (xfa == yfa) return 0; fa[xfa] = yfa; return 1; } int main() { cin >> m; for (int i = 1; i <= m; i++) cin >> mky[i], mky[i] *= mky[i]; cin >> n; for (int i = 1; i <= n; i++) cin >> tx[i] >> ty[i], fa[i] = i; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { int dx = tx[i] - tx[j], dy = ty[i] - ty[j]; edges.push_back({i, j, dx * dx + dy * dy}); } } int cnt = n - 1, mx = INT_MAX + 1, id = 0; sort(edges.begin(), edges.end()); while (cnt) { auto [u, v, w] = edges[id]; if (merge(u, v)) cnt --, mx = max(mx, w); id ++; } int ans = 0; for (int i = 1; i <= m; i++) ans += (mky[i] >= mx); cout << ans; return 0; } -
0

// 最小生成树 Kruskal算法 O(NlogN) #include<bits/stdc++.h> using namespace std; const int N=1e6+5; int n,m,k,tot,ans; int d[N],x[N],y[N],fa[N]; double mxd; pair<double,pair<int,int> >e[N]; //边集 int find(int u){ //并查集的找根 return fa[u]==u?u:fa[u]=find(fa[u]); } void kruskal(){ sort(e+1,e+k+1); //排序 for(int i=1; i<=n; i++) fa[i]=i; for(int i=1; i<=k; i++){ int x=find(e[i].second.first),y=find(e[i].second.second); if(x!=y){ fa[x]=y; mxd=e[i].first; //最大边权 if(++tot==n-1) break; } } for(int i=1; i<=m; i++)if(d[i]>=mxd)ans++; cout<<ans; } int main(){ cin>>m; //m个猴 for(int i=1; i<=m; i++) cin>>d[i]; cin>>n; //n颗树 for(int i=1; i<=n; i++) cin>>x[i]>>y[i]; for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(i!=j){ e[++k]={sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])),{i,j}}; } kruskal(); } -
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; int m,n; ll a[510],x[1010],y[1010]; ll dis(ll x,ll y,ll xx,ll yy){ return (x-xx)*(x-xx)+(y-yy)*(y-yy); } struct N{ ll x,y,v; }; vector<N> v; bool cmp(N a,N b){ return a.v<b.v; } int fa[1010]; int find(int x){ return fa[x]=(fa[x]==x?x:find(fa[x])); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>m; for(int i=1;i<=m;i++){ cin>>a[i]; a[i]*=a[i]; } cin>>n; for(int i=1;i<=n;i++){ cin>>x[i]>>y[i]; } ll mx=0; for(int i=1;i<=n;i++){ fa[i]=i; for(int j=i+1;j<=n;j++){ v.push_back({i,j,dis(x[i],y[i],x[j],y[j])}); } } sort(v.begin(),v.end(),cmp); int cnt=0; for(N i:v){ if(find(i.x)!=find(i.y)){ fa[find(i.x)]=find(i.y); mx=i.v; cnt++; } if(cnt==n-1)break; } int ans=0; for(int i=1;i<=m;i++){ if(a[i]>=mx)ans++; } cout<<ans; return 0; }
- 1
信息
- ID
- 4094
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 42
- 已通过
- 14
- 上传者