codeforces round 346div2 Polycarp and Hay搜索+并查集

/* 题目描述：给出一个n * m的矩阵，每个位置有一个数字a[i][j]，每个位置的数字在处理时可以减小或保持大小不变， 问这个矩阵中能否找到一个联通块，使得这个联通块中的数字在处理后大小相同，且这些联通块的总和 为k，且联通块中至少有一个元素的值与处理之前相同，如果存在这样的联通块，输出处理后矩阵，否则 输出NO 思路：可以枚举最终大小不变的那个元素是哪一个，假设当前枚举的是a[i][j]，那么就是从a[i][j]的位置向四周找到 一个联通块，要求这个联通块中所有元素的值大于等于a[i][j]，设这个联通块中元素的个数是cnt，那么如果 k能整除val且k/val <= cnt ， 那么这个联通块可以产生答案，可以通过一次dfs求出输出矩阵的情况。 那么，如何在不超时的情况下找到从a[i][j]向四周扩展时的联通快呢？可以先按照元素值从大到小的顺序为 矩阵中所有元素排序，然后进行上述枚举。在枚举的过程中，每求出一个元素的联通块，就把他们放到同一个 集合当中，这个集合中元素的个数可以记录下来。在枚举下一个元素时，如果该元素能延展到之前已经存在 的联通块，就可以把这个连通块并到当前元素所在联通块，因为是从大到小枚举的，先前存在的联通块中的元素 的大小一定大于等于后枚举出的联通块中元素大小。总之，已经处理过的联通块没必要再重新搜一次，在枚举 的后期，搜索只是在块与块之间进行的。 另外，这道题有一个常用的技巧，即利用并查集中的root的值代表这个并查集 */ #pragma warning(disable:4786) #pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<vector> #include<cmath> #include<string> #include<sstream> #define LL long long #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i) #define mem(a,x) memset(a,x,sizeof(a)) #define lson l,m,x<<1 #define rson m+1,r,x<<1|1 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1.0); const double eps=1e-6; const int maxn = 1e3 + 5; int a[maxn][maxn] , p[maxn * maxn] , sum[maxn * maxn] ; int ans[maxn][maxn] , vis[maxn][maxn] , n , m , cnt ,anscnt; int drx[] = {- 1, 1 , 0 , 0}; int dry[] = {0 , 0 , -1 , 1}; struct node { int val , x , y; bool operator < (const node & rhs) { return val > rhs.val; } }v[maxn * maxn]; bool ok(int x , int y) { if(x >=1 && x <= n && y >= 1 && y <= m) return true; return false; } int id(int x , int y) { return (x - 1) * m + y; } void init() { for(int i = 1 ; i <= n * m ; i++){ p[i] = i; } for(int i = 1 ; i<= n ; i++){ for(int j = 1 ; j <= m ; j++){ sum[ id(i , j) ] = 1; } } } int find(int x) { if(p[x] == x) return p[x]; else return p[x] = find(p[x]); } void merge(int x , int y) { int rx = find(x) , ry = find(y); if(rx == ry) return ; p[ry] = rx; } void dfs(int x , int y , int val , int root) { int nx , ny , fx , fy; for(int i = 0 ; i< 4; i++){ nx = x + drx[i]; ny = y + dry[i]; if(!ok(nx , ny) || a[nx][ny] < val ) continue; fx = find( id(nx , ny) ) ; fy = find( id(x , y) ); if(fx == fy || fx == root) continue; if(fx == id(nx , ny)){ int add = sum[ find(id(nx , ny)) ]; merge( root , id(nx , ny) ); dfs(nx , ny , val , root); sum[root] += add ; } else{ int add = sum[ find(id(nx , ny)) ]; merge( root , id(nx , ny) ); sum[root] += add ; } } cnt = max(cnt , sum[root]); } void dfs_ans(int x , int y , LL val) { if(cnt >= anscnt) return ; ++cnt; vis[x][y] = 1; ans[x][y] = val; int nx , ny; for(int i = 0 ; i<4 ; i++){ nx = x + drx[i]; ny = y + dry[i]; if(!ok(nx ,ny) || vis[nx][ny] || a[nx][ny] < val) continue; dfs_ans(nx , ny , val); } } int main() { LL k , ansval; scanf("%d%d%lld", &n , &m , &k); int c = 0; for(int i = 1; i<= n ; i++){ for(int j = 1 ; j <= m ; j++){ scanf("%d",&a[i][j]); node st = {a[i][j] , i , j}; v[++c] = st; } } sort(v + 1 , v + n * m + 1); init(); int p = 1 , flag = 0 , ansx , ansy; for(int i = 1 ; i <= n * m ; i++){ int x = v[i].x , y = v[i].y; int root = id(x , y); if(find(id(x , y) ) == id(x , y) ) dfs(x , y ,v[i].val , root); cnt = sum[ find(id(x , y)) ]; LL val = v[i].val , ss; if( k % val == 0){ ss = k / val; if( ss <= cnt ){ flag = 1; ansx = x; ansy = y; ansval = val; anscnt = ss; } } if(flag) break; } if(!flag){ puts("NO"); } else{ cnt = 0; dfs_ans(ansx , ansy , ansval); puts("YES"); for(int i= 1 ; i<= n ; i++){ for(int j = 1 ; j<= m ; j++){ printf("%d ",ans[i][j]); } printf("\n"); } } return 0; }