求助!!为何RE
  • 板块灌水区
  • 楼主变异哥斯拉
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/6/10 21:08
  • 上次更新2023/10/23 13:26:25
查看原帖
求助!!为何RE
415970
变异哥斯拉楼主2023/6/10 21:08
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+10;
struct node{
    int u,v,w;
    bool operator<(const node& x) const {
        return w<x.w;
    }
}edge[maxn];
int n,m,cnt,cnt2,k,ans,a[maxn][maxn],fa[maxn],vis[maxn];
int find(int x){
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++)if(s[j]=='1')a[i][j+1]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)if(a[i][j])++cnt;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i<n&&a[i][j]&&a[i+1][j]){
                edge[++k].u=(i-1)*m+j;edge[k].v=i*m+j;edge[k].w=1;
            }
            if(j<m&&a[i][j]&&a[i][j+1]){
                edge[++k].u=(i-1)*m+j;edge[k].v=(i-1)*m+j+1;edge[k].w=1;
            }
        }
    }
    sort(edge,edge+k);
    for(int i=1;i<=n*m;i++){
        fa[i]=i;vis[i]=0;
    }
    for(int i=1;i<=k;i++){
        int u=edge[i].u,v=edge[i].v,w=edge[i].w;
        int fu=find(u),fv=find(v);
        if(fu!=fv){
            fa[fu]=fv;ans+=w;cnt2++;
            if(cnt2==cnt)break;
        }
    }
    printf("%d %d",cnt-ans,ans);
    return 0;
}
2023/6/10 21:08
加载中...