3362076_ac_172ms_708k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <functional>
#include <algorithm>
#define maxn 16000

using namespace std;

struct Point
{
	int x, y;

	bool operator < (const Point &t)	const
	{
		return x < t.x || (x == t.x && y < t.y);
	}

	bool operator == (const Point &t)	const
	{
		return (x == t.x) && (y == t.y);
	}
};

int n, k;
Point point[maxn];
const int mov[][2] = { {1 , 0} , {-1 , 0} , {0 , 1} , {0 , -1} };
int p[maxn], rank[maxn];

int find(Point src, int to)
{
	int min, mid, max;

	min = 0;max = to - 1;
	while (min <= max)
	{
		mid = (min + max) >> 1;
		if (src == point[mid])
		{
			return mid;
		}
		if (src < point[mid])
		{
			max = mid - 1;
		}
		else
		{
			min = mid + 1;
		}
	}
	return -1;
}

int FIND_SET(int x)
{
	if (x!=p[x])
		return p[x] = FIND_SET(p[x]);
	else
		return p[x];
}

void LINK(int x,int y)
{
	if (rank[x] > rank[y])
	{
		p[y] = x;
	}
	else
	{
		p[x] = y;
		if (rank[x] == rank[y])
		{
			rank[y]++;
		}
	}
}

void UNION(int x,int y)
{
	LINK(FIND_SET(x),FIND_SET(y));
}

int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &point[i].x, &point[i].y);
	}
	sort(point, point + n);
	for (int i = 0; i < n; i++)
	{
		p[i] = i;
		rank[i] = 0;
		for (int j = 0; j < 4; j++)
		{
			int x = point[i].x + mov[j][0];
			int y = point[i].y + mov[j][1];
			int index = find((Point){x , y}, i);
			if (index != -1)
			{
				UNION(index, i);
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		FIND_SET(i);
	}
	sort(p, p + n);
	
	vector <int> ans;
	ans.clear();

	for (int i = 0; i < n; i++)
	{
		int cnt = 0;
		int j = i;
		while (j < n && p[j] == p[i])
		{
			cnt++;
			j++;
		}
		ans.push_back(cnt);
		i = j-1;
	}
	sort(ans.begin(), ans.end(), greater <int> ());
	int l = min((int)ans.size(), k);
	int num = 0;
	for (int i = 0; i < l; i++)
	{
		num += ans[i];
	}
	printf("%d\n", num);
	return 0;
}