BZOJ2034 【2009国家集训队】最大收益

题面

题解

第一眼：线段树优化连边的裸题

刚准备打，突然发现：

(1 leq S_i leq T_i leq 10^8)

这™用个鬼的线段树啊

经过一番寻找，在网上找到了一篇论文

大家可以去看一下，这里只提示大家用类似匈牙利算法贪心

这里还有代码

代码

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define clear(x, y) memset(x, y, sizeof(x))

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while(ch != '-' && (!isdigit(ch))) ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int maxn(5010);
struct node { int l, r, val; } p[maxn];
int n, val[maxn], match[maxn];
long long ans;
inline bool cmp_1(const node &a, const node &b) { return a.l < b.l; }
inline bool cmp_2(const node &a, const node &b) { return a.val > b.val; }

int hungary(int x, int y)
{
	if(val[y] > p[x].r) return 0;
	if(!match[y]) return (match[y] = x, 1);
	if(p[match[y]].r < p[x].r) return hungary(x, y + 1);
	else if(hungary(match[y], y + 1)) return (match[y] = x, 1);
	return 0;
}

int main()
{
	n = read();
	for(RG int i = 1; i <= n; i++) p[i] = (node) {read(), read(), read()};
	std::sort(p + 1, p + n + 1, cmp_1);
	for(RG int i = 1; i <= n; i++) val[i] = std::max(val[i - 1] + 1, p[i].l);
	for(RG int i = 1, j = 1; i <= n; i++)
	{
		while(j < n && val[j] < p[i].l) ++j;
		p[i].l = j;
	}
	std::sort(p + 1, p + n + 1, cmp_2);
	for(RG int i = 1; i <= n; i++)
		if(hungary(i, p[i].l)) ans += p[i].val;
	printf("%lld
", ans);
	return 0;
}