POJ 1456 Supermarket （贪心枚举 + 并查集）

vj链接

Solution

（暴力）按权值从大到小排序，从结束日期开始往前枚举判断是否能安排。
（并查集优化）待补。

代码

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
//#define int long long
#define lowbit(x) ((x) & (-x))
using namespace std;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef pair<double, int> pdi;
typedef double dd;
typedef long long ll;
const int MAXN = 10010;
const int MAXM = 3000010;
const dd eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;

int n, fa[MAXN];
pii a[MAXN];

int fd(int x){
	return x == fa[x] ? x : (fa[x] = fd(fa[x]));
}
int main()
{
	while (cin >> n)
	{
		if(n == 0)
		{
			printf("0\n");
			continue;
		}
		for (int i = 1; i <= 10004;i++)
			fa[i] = i;
		for (int i = 1; i <= n; i++)
			cin >> a[i].first >> a[i].second;
		sort(a + 1, a + 1 + n, greater<pii>());
		int sum = a[1].first;
		for (int i = 2; i <= n;i++)
		{
			for (int j = a[i].second; j >= 1;j--)
			{
				if (fd(j) != fd(a[1].second))
				{
					fa[fd(j)] = fd(a[1].second);
					sum += a[i].first;
					break;
				}
			}
		}
		printf("%d\n", sum);
	}
}