3 条题解

  • 0
    @ 2026-9-3 21:25:25
    #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
      @ 2026-6-15 14:58:57

      // 最小生成树 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
        @ 2026-5-9 15:10:16
        #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

        D129 最小生成树 Kruskal 算法[HAOI2006] 聪明的猴子

        信息

        ID
        4094
        时间
        1000ms
        内存
        128MiB
        难度
        6
        标签
        递交数
        42
        已通过
        14
        上传者