题目链接

题目大意

有一只猴子喜欢吃香蕉，但他只能在相邻的两棵香蕉树之间行动，如果两棵树是在横方向或竖方向相邻的，那么这就组成一个区域，这个区域内猴子可以随意走动，有人可以把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 16005int 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 16005int 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;
}