题目链接

题目大意

有一只猴子喜欢吃香蕉，但他只能在相邻的两棵香蕉树之间行动，如果两棵树是在横方向或竖方向相邻的，那么这就组成一个区域，这个区域内猴子可以随意走动，有人可以把k个区域连接起来，从而使猴子在这k个区域内随意行动，问猴子最多可以在多少棵树内走动？给定n个树的坐标，和k。

BFS+MAP

使用MAP存储已有点对，然后对输入的N个点每个进行bfs，找到和他相邻的所有点，并将已访问过的点打上标记，这样做虽然看起来复杂度不高，但是一般用map存储点对很容易T，果不其然这里就T了。

//TLE #define inf 0x3f3f3f3f #define ll long long #define vec vector<int> #define P pair<int,int> #define MAX 16005 int N, K, X[MAX], Y[MAX]; map<P, bool>ma; int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 }; int bfs(int sx, int sy) { int cnt = 1; queue<P> q; q.push(P(sx, sy)); ma[P(sx, sy)] = 0; while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (xx <= 0 || xx > 10000 || yy <= 0 || yy > 10000)continue; //这是一颗还没有访问过的树 if (ma.find(P(xx, yy)) != ma.end() && ma[P(xx, yy)] == 1) { ma[P(xx, yy)] = 0;//访问完他就不是树了 q.push(P(xx, yy)); cnt++; } } } return cnt; } int main() { scanf("%d %d", &N, &K); ma.clear(); for (int i = 0; i < N; i++) scanf("%d %d", &X[i], &Y[i]), ma[P(X[i], Y[i])] = 1; vec v; for (int i = 0; i < N; i++) { if (ma.find(P(X[i], Y[i])) != ma.end() && ma[P(X[i], Y[i])] == 1) v.push_back(bfs(X[i], Y[i])); } sort(v.begin(), v.end()); int res = 0; for (int i = v.size() - 1; i >= v.size() - K && i >= 0; i--) res += v[i]; cout << res << endl; }

并查集

当题目中好像需要存储点对时，如果map T了，我们不妨考虑一下一些优化的手段，常见的手段即按照横，纵坐标排序然后进行处理，这里也可以使用这种方法。

因为相邻的banana一定是横坐标相等纵坐标差1，或者纵坐标相等横坐标差1，那么我们将其分别按照横纵坐标排序，按x排序时统计y相邻的点，将他们分成多个组，然后按y排序时将x相邻的点所在的组合并起来。合并组别就用到了并查集这个高效的工具

//476K 204MS #define inf 0x3f3f3f3f #define ll long long #define vec vector<int> #define P pair<int,int> #define MAX 16005 int N, K, kind[MAX], cnt[MAX]; struct p { int x, y, id; }ps[MAX]; bool cmp(p p1, p p2) { if (p1.x == p2.x)return p1.y < p2.y; else return p1.x < p2.x; } bool ccmp(p p1, p p2) { if (p1.y == p2.y)return p1.x < p2.x; else return p1.y < p2.y; } int find(int k) { if (k == kind[k])return k; else return kind[k] = find(kind[k]); } void unite(int a, int b) { int p1 = find(b), p2 = find(a); if (p1 == p2)return;//同一集合，无需合并 kind[p1] = p2; cnt[p2] += cnt[p1]; cnt[p1] = 0; } int main() { scanf("%d %d", &N, &K); for (int i = 1; i <= N; i++) scanf("%d %d", &ps[i].x, &ps[i].y), ps[i].id = i; for (int i = 1; i <= N; i++)kind[i] = i, cnt[i] = 1; int i = 0, j = 0, res = 0; //按照x排序，找到x相同y相差为1的点 sort(ps + 1, ps + 1 + N, cmp); for (i = 2; i <= N; i++) { if (ps[i].x == ps[i - 1].x&&ps[i].y == ps[i - 1].y + 1) unite(ps[i - 1].id, ps[i].id); } //按照y排序，找到y相同x相差为1的点 sort(ps + 1, ps + 1 + N, ccmp); for (i = 2; i <= N; i++) { if (ps[i].y == ps[i - 1].y&&ps[i].x == ps[i - 1].x + 1) unite(ps[i - 1].id, ps[i].id); } sort(cnt + 1, cnt + N + 1); for (int i = N; i > N - K; i--) res += cnt[i]; cout << res << endl; }