自动搬运

查看原文

来自洛谷，原作者为

	Dream__Sky 欲买桂花同载酒，终不似，少年游。便邀东风揽明月，春不许，再回头

搬运于2025-08-24 22:35:13，当前版本为作者最后更新于2023-07-19 16:18:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：

带权二分图最大匹配，链式前向星，不会的请自行百度。

这道题难度虚高，其实就是带权二分图最大匹配模版。

因为警卫在一个时间段只能拦截一个人，这就相当于二分图左右两个点集每个点的度最大为 $1$，因此我们可以用最大匹配来做，不需要线段树等高级算法。

我们可以把一个点集看成每个小偷，另一个点集看做每一个时间段，在套上带权二分图最大匹配模版。为了让挽回的钱越多越好，我们可以用贪心的思想，先对每个小偷按照偷的钱（边权）排序，优先满足那些偷得最多的人，这样就能满足挽回的钱越多越好。

在每次二分匹配的过程中，我们可以加一个优化，每次搜索不必从头开始，可以从上一次搜到的点开始，这样可以节约时间，甚至能抢到最优解。

思路其实很简单，代码：

#include<bits/stdc++.h>
using namespace std;
const int M=2e7+5e6+10,N=5e3+10;
int n;
int h[M],nt[M],w[M],g[M],id=1;
struct ll{
	int x;
	int y;
	int z;
}a[N];
pair<int,int> match[N];
int st[N];
int ans;
inline void add(int a,int b,int c){
	g[id]=b;
	w[id]=c;
	nt[id]=h[a];
	h[a]=id++;
}//链式前向星建边
int s[N];
inline bool dfs(int num,int c){
	for(register int i=s[num];~i;i=nt[i]){
		int j=g[i];
		if(!st[j]){
			st[j]=1;
			if(!match[j].first||dfs(match[j].first,match[j].second)){
				match[j]={num,c};
				s[num]=i;
				return 1;
			}
		}
	}
	return 0;
}//带权二分图最大匹配,不会的请自行学习，这里不过多解释
int mi,mx;
inline int cmp(ll a,ll b){
	return a.z>b.z;
}
inline int read() {
	register int x=0;
	register char ch=getchar();
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
	}
	return x;
}
signed main()
{
	cin>>n;
	memset(h,-1,sizeof h);	
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	sort(a+1,a+n+1,cmp);//利用了贪心的思想，排序
	for(register int i=1;i<=n;i++){
		for(register int j=a[i].x;j<a[i].y;j++){
			add(i,j,a[i].z);//建边
		}
	}
	for(register int i=1;i<=n;i++){
		s[i]=h[i];//优化
	}
	for(register int i=1;i<=n;i++){
		memset(st,0,sizeof st);
		dfs(i,a[i].z);//对每个点进行匹配
	}
	for(register int i=1;i<=n;i++){
		ans+=match[i].second;//加上选上的边权
	}
	cout<<ans;
	return 0;
}

这里要感谢