BZOJ 2034: [2009国家集训队]最大收益 [贪心优化 Hungary]

时间：2022-05-31 16:22:50

2034: [2009国家集训队]最大收益

题意：\(n \le 5000\)个区间\(l,r\le 10^8\)，每个区间可以选一个点得到val[i]的价值，每个点最多选1次，求最大价值

线段树优化建边的做法见上一篇

论文



先把l,r离散化了，因为一个区间只选一个点，所以我们对于每个区间拿出一个点来就行了，方法是按l排序然后每个区间选左边界后的第一个未选点

当然这个点可能超出区间，所以我们要让区间与点匹配得到最大价值

  • 法1：裸上二分图最大权匹配，即使线段树优化建边还是承受不了
  • 法2：这个二分图很特殊，X的出边权值相同，我们可以贪心从大到小选择，用Hungary找增广路，复杂度\(O(n^3)\)
  • 法3：这个二分图超级特殊啊，X中每个点出边的集合是连续的一段，我们很方便比较两个点的可匹配点集合的大小，如果可匹配点集合更大的都找不到未盖点小的根本不用找啊！我们修改一下Hungary的过程，记下当前选到Y的哪个点now，如果now未匹配则匹配now，否则比较now的匹配点与当前点可匹配集合的大小，让更大的去找匹配。这样就省去了每个点遍历所有出边的过程，复杂度\(O(n^2)\)

总结

让深入分析问题的性质！ 贪心乱搞随便过

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define fir first

#define sec second

typedef long long ll;

const int N=1e4+5, INF=1e9;

inline ll read(){

    char c=getchar();ll x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n;

struct meow{

	int l, r, val;

	bool operator <(const meow &a) const {return val>a.val;}

}a[N];

bool cmp(const meow &a, const meow &b) {return a.l < b.l;}

int mp[N], m;

void disc() {

	sort(a+1, a+1+n, cmp);

	mp[++m]=a[1].l; int now=mp[m];

	for(int i=2; i<=n; i++)

		mp[++m] = max(now+1, a[i].l), now=mp[m];

	for(int i=1; i<=n; i++) {

		a[i].l = lower_bound(mp+1, mp+1+m, a[i].l) - mp;

		int t = lower_bound(mp+1, mp+1+m, a[i].r) - mp;

		a[i].r = mp[t] == a[i].r ? t : t-1;

	}

}

int le[N];

bool find(int u, int now) {

	if(now>a[u].r) return false;

	if(!le[now]) {le[now]=u; return true;}

	if(a[u].r > a[le[now]].r) return find(u, now+1);

	else {

		if(find(le[now], now+1)) {le[now]=u; return true;}

		else return false;

	}

}

void solve() {

	sort(a+1, a+1+n);

	ll ans=0;

	for(int i=1; i<=n; i++) if(find(i, a[i].l)) ans+=a[i].val;

	printf("%lld", ans);

}

int main() {

	freopen("in","r",stdin);

	n=read();

	for(int i=1; i<=n; i++) a[i].l=read(), a[i].r=read()-1, a[i].val=read();

	disc();

	solve();

}

相关文章