网站建设费用自建最新资讯热点

NOIP2023模拟1联测22 爆炸

题目大意

​ 自己看

思路

当一个炸弹被引爆后，它的方向是固定的。如果被竖着引爆，那么应该选择横着引爆，否则选择竖着引爆，这是显然 的。

考虑对于每个炸弹 $(i,j)$ 将第 $i$ 行和第 $j$ 列连边

对于每个水晶 $(i,j)$ 如果 $i$ 行和 $j $ 列不在一个连通块内，各自的连通块的贡献分别加上 $1$ ，否则加一个就好了

枚举每一个连通块，如果能够形成一个环，那么这个连通块的答案就是已经统计过的贡献

否则这个连通块的答案就是损失一行或者一列的水晶

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 3005;
int n , m , k , b , mp[N][N] , fa[N << 1] , a[N << 1] , flg , vis[N << 1] , min1 , sum[N << 1] , ans , cnt;
char c;
vector<int> v[N << 1];
int find (int x) { return fa[x] != x ? fa[x] = find (fa[x]) : x; }
void dfs (int x , int fa) {if (flg) return;if (vis[x]) {flg = 1;return;}vis[x] = 1;if (v[x].size() == 1) min1 = min (min1 , a[x]);for (auto it : v[x])if (it != fa)dfs (it , x);
}
int main () {freopen ("boom.in" , "r" , stdin);freopen ("boom.out" , "w" , stdout);scanf ("%d%d%d%d" , &n , &m , &k , &b);fu (i , 1 , n + m) fa[i] = i;fu (i , 1 , n) {fu (j , 1 , m) {c = getchar ();while (c != '.' && c != 'k' && c != 'b') c = getchar ();if (c == '.') mp[i][j] = 1;else if (c == 'b') {mp[i][j] = 2;v[i].push_back(j + n);v[j + n].push_back(i);fa[find (i)] = find (j + n);}]]]elsemp[i][j] = 3;}}fu (i , 1 , n) {fu (j , 1 , m) {if (mp[i][j] == 3) {sum[find (i)] ++;if (find (i) != find (j + n)) {sum[find (j + n)] ++;a[i] ++ , a[j + n] ++;} }}}// fu (i , 1 , n + m) cout << a[i] << " ";// return 0;fu (i , 1,  n + m) {if (vis[i]) continue;min1 = INT_MAX , flg = 0;dfs (i , 0);if (flg) ans = max (ans , sum[find (i)]);else ans = max (ans , sum[find (i)] - min1);}printf ("%d" , ans);return 0;
}