【Codeforces 659F】Polycarp and Hay
Zarxdy34
posted @ 2016年4月04日 13:26
in Codeforces
with tags
并查集
, 651 阅读
把点从大到小排序，然后并查集维护连通块大小，检查是否有解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int maxn=1010,maxv=1000010;struct Node {int x,y,h;}P[maxv];bool cmp (const Node &a,const Node &b) {return a.h<b.h;}int fa[maxv],c[maxv];int map[maxn][maxn];int ans[maxn][maxn];LL k;int n,m,cnt;int p(int x,int y) {return (x-1)*m+y;}int Find(int x) {return x==fa[x]?x:fa[x]=Find(fa[x]);}void DFS(int h,int v,int x,int y){ ans[x][y]=h;cnt--; if (!cnt) return; if (x>1 && Find(p(x-1,y))==v && !ans[x-1][y]) DFS(h,v,x-1,y); if (!cnt) return; if (x<n && Find(p(x+1,y))==v && !ans[x+1][y]) DFS(h,v,x+1,y); if (!cnt) return; if (y>1 && Find(p(x,y-1))==v && !ans[x][y-1]) DFS(h,v,x,y-1); if (!cnt) return; if (y<m && Find(p(x,y+1))==v && !ans[x][y+1]) DFS(h,v,x,y+1);}int main(){ scanf("%d%d%I64d",&n,&m,&k); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { scanf("%d",&map[i][j]); int v=p(i,j); P[v].x=i;P[v].y=j; P[v].h=map[i][j]; fa[v]=v;c[v]=1; } sort(P+1,P+1+n*m,cmp); for (int i=n*m;i;i--) { int x=P[i].x,y=P[i].y,h=P[i].h,v=p(x,y); if (x>1 && map[x-1][y]>=map[x][y] && Find(v)!=Find(p(x-1,y))) c[Find(v)]+=c[Find(p(x-1,y))],fa[Find(p(x-1,y))]=Find(v); if (y>1 && map[x][y-1]>=map[x][y] && Find(v)!=Find(p(x,y-1))) c[Find(v)]+=c[Find(p(x,y-1))],fa[Find(p(x,y-1))]=Find(v); if (x<n && map[x+1][y]>=map[x][y] && Find(v)!=Find(p(x+1,y))) c[Find(v)]+=c[Find(p(x+1,y))],fa[Find(p(x+1,y))]=Find(v); if (y<m && map[x][y+1]>=map[x][y] && Find(v)!=Find(p(x,y+1))) c[Find(v)]+=c[Find(p(x,y+1))],fa[Find(p(x,y+1))]=Find(v); if (k%h==0 && k/h<=c[Find(v)]) { puts("YES"); cnt=k/h; DFS(h,Find(v),x,y); for (x=1;x<=n;x++) { for (y=1;y<m;y++) printf("%d ",ans[x][y]); printf("%d\n",ans[x][m]); } return 0; } } puts("NO"); return 0;} |
评论 (0)
