P8021 题解

Dream__Sky · 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;
}

这里要感谢 @yushucheng123 大佬提供的思路。