2 条题解
-
0
bfs是需要优化的，具体看我进队的处理
#include<bits/stdc++.h> #pragma GCC optimize ("Ofast") using namespace std; const int N=1100; inline int read() { int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } int n, m, ans, tsp, res, mp[N][N], now[N][N]; bool v[N][N]; int dx[4]={1, -1, 0, 0}; int dy[4]={0, 0, -1, 1}; struct node {int x, y, c;} a[N*N]; int len; bool cmp(node a, node b) {return a.c<b.c;} void bfs(int sx, int sy) { deque<node> q; q.push_back({sx, sy}); ans++; v[sx][sy]=True; now[sx][sy]=mp[sx][sy]; while(q.size()) { auto t=q.front(); q.pop_front(); for(int i=0;i<4;i++) { int xx=t.x+dx[i], yy=t.y+dy[i]; if(xx<=0||yy<=0||xx>m||yy>n) continue; if(mp[xx][yy]>0&&now[t.x][t.y]>mp[xx][yy]) continue; int h=max(now[t.x][t.y], abs(mp[xx][yy])); if(h<now[xx][yy]) { now[xx][yy]=h; if(!v[xx][yy]) { v[xx][yy]=True; if(q.size()&&now[xx][yy]<=now[q.front().x][q.front().y]) q.push_front({xx, yy}); else q.push_back({xx, yy}); } } } v[t.x][t.y]=False; } } int main() { m=read(); n=read(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { mp[i][j]=read(); if(mp[i][j]>0) a[++len]={i, j, mp[i][j]}; } res=len, ans=0; sort(a+1, a+1+len, cmp); memset(now, 63, sizeof(now)); for(int i=1;i<=len;i++) { int x=a[i].x, y=a[i].y; if(now[x][y]>mp[x][y]) bfs(x, y); } printf("%d\n", ans); return 0; }并查集的代码也贴上来了，仅供参考
#include<bits/stdc++.h> using namespace std; #define re register const int maxn=1e3+5; inline int read() { char ch=getchar();bool f=0;int x=0; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1; for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48); if(f==1)x=-x;return x; } void print(int x) { if(x<0) putchar('-'),x=-x; if(x>9) print(x/10); putchar(x%10+'0'); } int n,m,a[maxn][maxn],f[maxn][maxn],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},fa[maxn*maxn],s[maxn*maxnn],ans=0; struct node { int x,y,num; }b[1000005]; bool cmp(node a,node b){return a.num<b.num;}int getf(int x){if(fa[x]==x)return x;fa[x]=getf(fa[x]);return x;} void gett(int x,int y) {x=getf(x),y=getf(y);if(x==y)return ;fa[x]=y;s[y]|=s[x];} int id(int x,int y){return (x-1)*m+y;} signed main() { n=read(),m=read();memset(a,0x3f,sizeof a); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=read(); if(a[i][j]<0)a[i][j]=abs(a[i][j]); else f[i][j]=1; b[id(i,j)]=(node){i,j,a[i][j]}; fa[id(i,j)]=id(i,j); } sort(b+1,b+id(n,m)+1,cmp); for(int i=1;i<=n*m;i++) { for(int j=0;j<4;j++) { int tx=b[i].x+dx[j],ty=b[i].y+dy[j]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]<=b[i].num)gett(id(tx,ty),id(b[i].x,b[i].y)); } if(i==n*m||b[i].num!=b[i+1].num) { for(int j=i;j>=1&&b[j].num==b[i].num;j--) { if(f[b[j].x][b[j].y]) { int h=getf(id(b[j].x,b[j].y)); if(!s[h])s[h]=1,ans++; } } } } cout<<ans; return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:02:44
bfs是需要优化的，具体看我进队的处理
#include<bits/stdc++.h> #pragma GCC optimize ("Ofast") using namespace std; const int N=1100; inline int read() { int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w; } int n, m, ans, tsp, res, mp[N][N], now[N][N]; bool v[N][N]; int dx[4]={1, -1, 0, 0}; int dy[4]={0, 0, -1, 1}; struct node {int x, y, c;} a[N*N]; int len; bool cmp(node a, node b) {return a.c<b.c;} void bfs(int sx, int sy) { deque<node> q; q.push_back({sx, sy}); ans++; v[sx][sy]=True; now[sx][sy]=mp[sx][sy]; while(q.size()) { auto t=q.front(); q.pop_front(); for(int i=0;i<4;i++) { int xx=t.x+dx[i], yy=t.y+dy[i]; if(xx<=0||yy<=0||xx>m||yy>n) continue; if(mp[xx][yy]>0&&now[t.x][t.y]>mp[xx][yy]) continue; int h=max(now[t.x][t.y], abs(mp[xx][yy])); if(h<now[xx][yy]) { now[xx][yy]=h; if(!v[xx][yy]) { v[xx][yy]=True; if(q.size()&&now[xx][yy]<=now[q.front().x][q.front().y]) q.push_front({xx, yy}); else q.push_back({xx, yy}); } } } v[t.x][t.y]=False; } } int main() { m=read(); n=read(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { mp[i][j]=read(); if(mp[i][j]>0) a[++len]={i, j, mp[i][j]}; } res=len, ans=0; sort(a+1, a+1+len, cmp); memset(now, 63, sizeof(now)); for(int i=1;i<=len;i++) { int x=a[i].x, y=a[i].y; if(now[x][y]>mp[x][y]) bfs(x, y); } printf("%d\n", ans); return 0; }并查集的代码也贴上来了，仅供参考
#include<bits/stdc++.h> using namespace std; //static char buf[1000000],*p1=buf,*p2=buf; //#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++ #define re register const int maxn=1e3+5; inline int read() { char ch=getchar();bool f=0;int x=0; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1; for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48); if(f==1)x=-x;return x; } void print(int x) { if(x<0) putchar('-'),x=-x; if(x>9) print(x/10); putchar(x%10+'0'); } int n,m,a[maxn][maxn],f[maxn][maxn],dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},fa[maxn*maxn],s[maxn*maxn],ans=0; struct node { int x,y,num; }b[1000005]; bool cmp(node a,node b){return a.num<b.num;} int getf(int x){if(fa[x]==x)return x;fa[x]=getf(fa[x]);return fa[x];} void gett(int x,int y) { x=getf(x),y=getf(y);if(x==y)return ; fa[x]=y;s[y]|=s[x]; } int id(int x,int y){return (x-1)*m+y;} signed main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout); n=read(),m=read();memset(a,0x3f,sizeof a); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=read(); if(a[i][j]<0)a[i][j]=abs(a[i][j]); else f[i][j]=1; b[id(i,j)]=(node){i,j,a[i][j]}; fa[id(i,j)]=id(i,j); } sort(b+1,b+id(n,m)+1,cmp);</p>for(int i=1;i<=n*m;i++) { for(int j=0;j<4;j++) { int tx=b[i].x+dx[j],ty=b[i].y+dy[j]; if(a[tx][ty]<=b[i].num)gett(id(tx,ty),id(b[i].x,b[i].y)); } if(b[i].num!=b[i+1].num) { for(int j=i;;j--) { if(b[j].num!=b[i].num)break; if(f[b[j].x][b[j].y]) { int h=getf(id(b[j].x,b[j].y)); if(!s[h])s[h]=1,ans++; } } } } cout<<ans; return 0;}
- 1
