一口气看完 80% 反悔贪心

A6TVhmj · 2026-08-11 16:41:42 · 算法·理论

提示：下文的很多题目往往还有费用流和 WQS 二分的做法，三者本质都是针对收益递减（凸性）开发的。反悔贪心本质也是一种模拟费用流。本文将直接从反悔贪心的角度思考题目 （故意不会网络流），目的是锻炼思维而非套用网络流模板这类的。

而相比纯贪心，反悔贪心才能处理物品互相干涉的情况。它的本质，就是通过创造反悔操作，把互相干涉的物品，转化成互不干涉的收益。

据我总结，思考反悔贪心的通用思路是：

哪些方案可以让选择数增加 1，这种方案的收益是多少？

• 对于普通贪心，增加 1 可能就是多选一个。
• 而对于反悔贪心，可能会出现放弃一个、选另外两个的情况。想明白如何增加 1，题目就会了一大半。
• 除了以上情况，有时还会有不增加选择数目的反悔（一换一），这种替换操作虽然不增加选的数目，但是会让全局情况更优，有利于之后选更多。

具体情况具体讨论，于是我便总结了很多类经典的例题。

限时的工作安排和它的 N 倍经验

难度：黄绿左右 | 时间复杂度：O(n\log n)

题目：

P3093&P2949 多个工作，有收益和截止时间，每个单位时间只能完成一个工作，求最大收益。

P4053 多个工作，有完成所需时长和截止时间，求最多完成工作数。

P11457&P14097&P11328&P15699 多个工作，有完成所需时长和开始工作的最晚时间，求最多完成工作数。

P8769 多种巧克力，有价格、保质期和数量，求够吃 x 天的最少花费。

P2107 数轴上 0 右侧有多个工作，有坐标和耗时。从 0 出发，要求“总耗时 + 走到的最远坐标”不超过总时限 m，求最多能完成的任务数。

（拓展题）P4511 维护多个工作，有收益和截止时间，每个单位时间只能完成一个工作，支持插入工作，删除工作和查询最大收益。

解法：

先按照截止时间升序排序。

如果只用纯贪心“能选就选”，那么当前面已经选满时，后面出现更优任务就会出错。如果无法直接加入又还想把它选进来，只可能通过替换当前已选集合中的某一个任务实现，而为了让收益更大，替换的任务一定是当前已选集合中最差的那个。用优先队列维护。

总结两种选择方案：如果截止时间前还能做，直接收益增加 a_i，否则如果当前任务优于已选集合中最差的那个，弹出最差的换成这个，收益增加 a_i - \min(\text{已选})。

::::success[P2949 代码]

#include<bits/stdc++.h>
using namespace std;
struct wo{long long d,p;}a[100005];
bool cmp(wo a,wo b){return a.d<b.d;}
long long n,x,y,ans;
priority_queue<long long,vector<long long>,greater<long long> > q;//小根堆找最差情况
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        a[i]={x,y};
    }
    sort(a+1,a+n+1,cmp);
    int t=0;//已做任务数
    for(int i=1;i<=n;i++){
        if(t<a[i].d)q.push(a[i].p),t++;//还有空闲时间
        else if(!q.empty()&&a[i].p>q.top())q.pop(),q.push(a[i].p);
    }
    while(!q.empty())ans+=q.top(),q.pop();//统计答案
    cout<<ans;
    return 0;
}

::::

其他几题思维大同小异，不同的是需要反悔的条件和最差工作的定义，例如 P4053 要维护的就是最耗时的工作，P8769 要维护最贵的巧克力。

区分：限制开始最晚时间 VS 限制截止时间

P4053 给的是截止时间，这种情况直接按照截止时间排序即可。

P11457&P14097&P11328&P15699 给定了工作开始的最晚时间，这个时候需要先利用 \text{最晚开始时间}+\text{用时}=\text{截止时间} 进行转换成 P4053 然后再做。否则会出现顺序颠倒导致漏解，或反悔替换后依然超时的非法方案。

P2107 相当于是一个拥有全局固定时间上限的工作安排。只不过从上一栋楼走到下一栋楼的差值，相当于强制不能反悔的耗时任务。把差值算进总耗时后，它和普通工作安排的代码逻辑就一样了。

P4511 可以用线段树分治来离线做，另一种在线做法：用线段树维护前缀空闲容量（插入/删除对应后缀 -1/+1），并维护已选和未选集合。插入时会发生某个位置容量变成负数，此时必须把一个工作放入未选集合（位置必须在第一个负数之前且收益最小）。删除会腾出时间，可以从“未选集合”选新的（位置必须在最后一个 0 之后且收益最大）。

背包反悔问题

难度：黄到青（思维中等，代码简单）| 时间复杂度：O(n\log n)

这类问题非常像背包 DP，但由于物品之间存在特殊的属性（比如可替换、有门槛、有差价），使得我们可以贪心地选择，在容量不够时通过“退换货”反悔。

看完你可能会觉得和前面的“限时的工作安排”有点像。其实，如果把时间也看作一种费用，背包反悔问题确实可以看作是一种更广义的“限时工作安排”——这说明时间确实就是金钱（笑）。

题目：

P14635 买多种糖果，每种有第奇数颗和第偶数颗的两种价格 x,y，求 m 元最多买几颗。

P3045 每种牛有原价和优惠价，只有 k 张能让原价变为优惠价的优惠券，求 m 元最多买几头。

P4823 小矮人搭人梯逃跑，每个人有高度 a 和手臂长 b，人梯高度是人梯里人的总高度加逃跑者的手臂长度。高度达到 H 时，逃跑者就能逃跑并离开人梯，求最多逃几个。

P3545 每天上午提供 a 单位资源，中午如果资源充足可以选择消耗 b 单位资源（a,b 每天变化），求最多可以消耗几次并给出方案。

解法：

由于代码实现简单，题解丰富，这里只讲思路。

P14635：

需要想到可以把两颗同种糖果看成“套餐”x+y 元。只买最便宜的“套餐”和单颗糖果就行。

假设一开始全买最便宜的“套餐”，每次反悔少买一份“套餐”，改买所有没买过的种类中最便宜的单颗糖果，记录新的答案 \text{单颗数}+\text{套餐数} \times 2。最后输出最大值。

（由于价格单调，连堆都不用，直接排序即可）

P3045：

先按优惠价升序排序，把 k 张优惠券全用完。

之后买牛有两种买法：原价购买和反悔：抢买过的牛的优惠券（显然抢优惠价差最小的），用优惠价买牛。每次选两种里花费最少的。用三个堆维护即可（已买且用券的优惠价差，未买原价，未买优惠价）。

P4823：

先按逃跑难度 a+b 升序排序，逐个尝试逃跑。

之后要么高度达到就直接跑，要么高度不够就反悔：将逃跑者身体高度最高的拉回垫着，然后让当前逃跑者逃跑，这样虽然一换一没增加人数，但是增加了人梯的身体高度，使得之后的人更可能逃跑。用大根堆维护逃跑者身体高度。

P3545：

可以理解为提供资源是增加背包容量，消耗看成物品。贪心就是资源足够就一定消耗，反悔是用一个更小的消耗替换之前的最大的消耗（像上一题，虽然选的消耗次数不变，但是背包占用容量变少了，使得之后的消耗更有可能进行）。

不相邻种树和它的 N 倍经验

难度：青（接下来的题目有水紫） | 时间复杂度：O(k\log n)

题目：

P1484 给定整数序列，选最多 k 个数要求不相邻，求总和最大值。

P1792 给定环形整数序列，选 k 个数要求不相邻，求总和最大值。

P3620 在数轴上给定多个有序点，选 k 对互不相交的点配对，求最小距离和。

P14374 给定整数序列，对于所有 1 \le k \le \dfrac{n}{2}，选 k 个数要求不相邻，求总和最大值。

P10478&P6821 给定整数序列，选出最多 k 个不相交连续段，求总和最大值。

解法：

先说 P1484，我们发现纯贪心（每次选可选的数中最大的）这个思路是错的。例如序列 98,99,97，贪心会只选 99 而不是更好的 98+97=195，于是我们可以想到，将“反悔”作为另一种方案，放弃选中间而改选两边，这样的收益有多少？因为我们放弃了中间的，所以收益是 a_{p-1}+a_{p+1}-a_p。

总结两种选择方案：选中间的和放弃中间的选两边的，两种都能让我们多选一个数。

实现方面：维护收益大根堆（为了支持任意删除我用了 set，另一种实现是优先队列+懒惰删除），初始放入所有数和对应收益，取出时删除堆内两侧的收益，放入反悔收益。重复 k 次，如果不强制正好 k 个，发现最大收益为负即可结束。同时，由于每次选择会删除左右两边的数，我们需要链表来维护每个下标的左侧和右侧，可以用手写双向链表或者用 set 模拟。

::::success[P1484 代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
int n,k,a[maxn],ans;
set<pair<int,int>>s;
set<int> p;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],p.emplace(i),s.emplace(a[i],i);
    a[0]=a[n+1]=-1e15;p.emplace(0),p.emplace(n+1);//-1e15 防止边界反悔
    for(int i=1;i<=k;i++){
        auto [x,j]=*s.rbegin();//set 取最大
        if(x<0)break;//提前退出
        auto it=p.find(j);int l=*prev(it),r=*next(it);
        s.erase(prev(s.end()));
        ans+=x,s.emplace(a[j]=a[l]+a[r]-x,j);//反悔收益
        s.erase({a[l],l}),s.erase({a[r],r});//两边不能选了
        p.erase(l),p.erase(r);
    }
    cout<<ans;
    return 0;
}

::::

对于环形的情况，修改链表/set 让下标 1 的左边是 n，下标 n 右边是 1 就行。

对于 P3620，很容易发现选相邻点配对是最优的，得到相邻两点的距离后转化成了经典问题。

对于选连续段的情况，可以把一段区间当一个点来反悔：将连续正数合并、连续负数合并，得到正负交替序列。初始选择所有的正数段，通过两种方式减少段数：删除一段和让负数段合并相邻两个正数段。把两种收益放入小根堆像种树题一样维护即可。

多状态转移问题

难度主要在代码细节：紫黑 | 时间复杂度：O(S \log n)

别被这些题目的颜色吓到，思路依然是那句话：想清楚“选一个”和“退一个换两个”这两种情况怎么增加答案。只是这里情况变多了，需要用几个堆分别维护处于不同状态的元素，每次比较所有堆的最优方案，把物品在堆之间“转移”（相当于反悔贪心自己的状态转移，类型上有点像动态规划）。思路不难，但写起来要同步维护好几个堆的进出，细节多，需要留神。

题目：

（热身题）P14361 三个社团 n 个人，每个人对每个社团有满意度，分配每个人到社团，要求每个社团人数小于等于 \dfrac{n}{2}，求总满意度最大值。

CF436E 多个关卡，给出每个打到一星和二星的所需时间 a,b，求总共取得 m 颗星最低耗时和对应方案。

P5470 两个长度相同的整数序列 A,B，各选 k 个数，至少 l 对下标相同的，求最大总和。

（选做）CF739E 用 a 个普通球和 b 个高级球捕捉宝可梦，两种球捕捉每只精灵成功率不同且可叠加，每只精灵每种球最多只能扔一次。求捕捉数最大期望。

解法：

P14361：

看似是复杂的三个社团互相干涉，但是我们依然从贪心入手再考虑反悔。先把每个人按照最满意的社团分配。

此时可能直接解决了，也可能不符合人数要求。不难看出最多只有一个社团人数大于 \dfrac{n}{2}。

因此我们只用对不符合要求的社团进行反悔：为里面的每个人计算转社的最小满意度亏损（对比转到另外两个社团的满意度减少值，两者取最小），一直反悔转社直到社团符合要求。由于人数要求上限是 \dfrac{n}{2}，转社一定不会导致其他社团人数超限。

CF436E：

这题看着吓人，我们顺着“增加 1 颗星”的思路走就很简单了。

直接增加一颗星的方案很简单：

• 两种贪心：把关卡打到一星，耗时 a；从一星打到二星，耗时 b-a；

但是我们还要想到，可能有的关卡打到一星很不值，打到二星特别划算，这时候就需要一个能直升二星的方案，也就是反悔：

• 两种反悔：反悔掉一个一星关卡，把另外一个关卡直接打到二星，耗时 b-a_{\max}；把一个二星关卡反悔到一星，把另外一个关卡打到二星，耗时 b-(b-a)_{\max}。
• 两种反悔情况可以合并，都是降一颗星升两个星，耗时 b-\max(a_{\max},(b-a)_{\max})。

于是一共三种方案，每次选择耗时最短的方案，我们只需要维护四个堆（从空打到一星的 a，从一星打到二星的 b-a，从空打到二星的 b，降一颗星的 a_{\max} 和 (b-a)_{\max}），让各种状态的关卡在里面流转就行。

::::success[CF436E 代码]

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
int n,w,s[maxn];long long ans;
pair<int,int> l[maxn];
set<pair<int,int>> a,b,mxb,mnb;
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>l[i].first>>l[i].second;
        a.emplace(l[i].first,i);
        mnb.emplace(l[i].second,i);
    }
    for(int i=1;i<=w;i++){
        int x=2e9,y=2e9,z=2e9;//计算三种方案收益
        if(!a.empty())x=a.begin()->first;//0->1
        if(!b.empty())y=b.begin()->first;//1->2
        if(!mxb.empty()&&!mnb.empty())z=mnb.begin()->first-mxb.rbegin()->first;//反悔：-1,0->2
        ans+=min(min(x,y),z);
        if(x<=y&&x<=z){
            auto [tmp,j]=*a.begin();
            mxb.emplace(*a.begin());
            a.erase(a.begin());
            mnb.erase({l[j].second,j});
            b.emplace(l[j].second-l[j].first,j);
            s[j]=1;//记录方案，j有一星了
        }else if(y<=x&&y<=z){
            auto [tmp,j]=*b.begin();
            mxb.erase({l[j].first,j});
            mxb.emplace(*b.begin());
            b.erase(b.begin());
            s[j]=2;//记录方案，j有二星了
        }else{
            auto [tmp,j]=*mxb.rbegin();
            mxb.erase(prev(mxb.end()));
            if(s[j]==1){ //降一颗星分两种情况，这里是一颗星降到无
                b.erase({l[j].second-l[j].first,j});
                a.emplace(l[j].first,j);
                mnb.emplace(l[j].second,j);
            }else{//否则就是两颗星降一颗
                b.emplace(l[j].second-l[j].first,j);
                mxb.emplace(l[j].first,j);
            }
            auto [tmp2,k]=*mnb.begin();
            mnb.erase(mnb.begin());
            a.erase({l[k].first,k});
            mxb.emplace(l[k].second-l[k].first,k);
            s[j]--,s[k]=2;//j减少一颗，k打到二星
        }
    }
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++)cout<<s[i];
    return 0;
}

::::

P5470：

先无视相同下标限制，按照最大的各选 k 个。发现相同下标对数可能不够，所以要考虑增加一对相同下标的方案，先是三种很容易想到的正常贪心：

这道题能放弃一对增加两对吗？肯定是可以的，也就是反悔方案：

• 反悔：移除一对下标相同的，A 补一个 B 有的下标，B 补一个 A 有的下标，收益 b_{a\max}+a_{b\max}-(ab)_{\min}。

一共四种方案，根据推出来的花费，需要维护六个堆：

• 两个都没有的大根堆，两个都有的小根堆；
• 仅 A 选了的大根堆（记录对应 b_{\max} 值），仅 A 选了的小根堆（记录 a_{\min} 值）；
• 仅 B 选了的大根堆（记录对应 a_{\max} 值），仅 B 选了的小根堆（记录 b_{\min} 值）。

四种状态为啥需要六个堆？

“只选 A”这批下标要接受两种情况：一是自己太小，在反悔时会被换掉（按 a 值找最小），二是选择对应的 B 收益很大，可以凑成一对（按 b 值找最大）。这是两个完全不同的问题，只能拆成两个堆分别判断。“只选 B”的情况也是同理。四种状态里有两种状态要被问两次，堆的数量自然就从四个变成了六个。

可以看出，在两个序列地位平等时，用于收益和反悔的堆有种对顶的感觉。做法相似，只要想明白“怎么凑出一对相同的”就行。只附提交记录 P5470 提交记录。

CF739E：

一般会用 WQS 二分，但是我是反悔贪心的粉丝反悔贪心也可以做。

由于同时考虑增加两种球太复杂，所以贪心先给普通球概率最高的 a 个装普通球。然后就只用考虑增加一颗高级球的方案了，一共三种：

• 扔给没给过球的宝可梦；补扔给有普通球的宝可梦；
• 反悔：把普通球替换成高级球，并将普通球扔给没给过球的宝可梦。

需要维护四个堆：

• 普通情况：直接接高级球的增量；有普通球接高级球的增量；
• 反悔情况：高级球替换普通球的增量；接普通球的增量。

这道题各种情况的收益建议自己推一遍，会有很大收获，适合学过期望且想更加熟悉多状态反悔的进阶者。（但是代码盲猜就没有人会用反悔贪心写了，需要代码的私信作者）

括号选择收益问题

难度：绿以上 | 时间复杂度：O(n\log n)

一般是用“线段树模拟费用流”解决，但是本质思维还是简单的反悔贪心（只是多了数据结构维护），而且有些题有更简单的解法。

题目：

P16279 n 位十进制正整数，保证 n 为偶数，每次删除相邻两位，获得删除的两位数得分，求最大得分。

P4694&CF802M3 生产 x 个相同物品，要经历 AB 两道工序，B 在 A 之后，一共 n 天，每天两种工序的花费是变化的，每种工序每天只能做一个物品。求最小花费。

解法：

可能有人会想用区间 DP 做，但是数据范围不允许（笑）。

P16279：

不难发现，每次删除相邻两位组成两位数 10x+y，这说明一半的数字要当十位，另一半当个位。因为总和固定，所以要让得分最大，就要让当十位的数字总和最大。

但是不能无脑选前 n/2 大的数字当十位，限制来自括号匹配：把当十位看作左括号，当个位看作右括号，选择方案肯定是一个合法的括号序列。而一个括号序列合法当且仅当：对于任意前缀，右括号（个位）的数量绝对不能超过一半。

于是反悔贪心呼之欲出：我们贪心地假设每个数字都想当个位。每扫描到一位，检查当前的“个位”是否大于一半，一旦满足，就必须挑一个数反悔成十位（肯定是尽可能大的）。维护大根堆即可解决。

P4694&CF802M3：

不扯 WQS 二分和费用流，反悔贪心+线段树思路还是很简单的。

首先贪心大家肯定都会，怎么反悔呢？按照括号序列的思路，A 是左括号，B 是右括号，反悔便是在一堆 () 中间插入反向配对 )(，怎么判断是否在中间？可以用最小值线段树维护区间“半成品数”。每次配对相当于在区间 [A,B-1] 进行区间 +1。同时维护区间最优左括号、最优右括号、最优贪心和最优反悔。

但是这里也有限制，反悔的区间中间不能有 0，也就是必须用半成品才能反悔。而最小值和懒标记又有关系不好维护。所以我们必须假设当前区间是有 0 的。同时维护合法（不跨最低点）与不合法反悔（跨最低点），一旦通过实锤某半边区间的最小值严格大于另一半（说明大的半边绝对没有 0），不合法的就可以改邪归正，被接纳进合法的反悔答案中。

代码要注意的事项很多，（所以我放代码也没人想看）。但是也体现了费用流这种高深的知识完全可以被思维化简，而不是将其奉为一道高高在上的紫题。

都是括号收益问题，第二个为啥要用线段树？

区别不在于“能不能存位置”——堆可以把位置和数值绑在一起。真正的差别是：反悔要不要对一段区间做查询和修改。

P16279 的反悔是“选一个之前的数改成十位”，只关心选出的数够不够大，跟它在哪一位无关，堆就够。

而 P4694 的反悔是往一对已配好的括号中间插入一对反向的，新的这一对必须落在某个仍有半成品的区间 [A,B) 内部（区间最小值非零），找到后还要对整段做加减。堆存得下位置，存不下区间最值，也做不了区间修改，只能用线段树。

::::success[P4694&CF802M3 代码]

#include<bits/stdc++.h>
#define tp tr[p]
#define pli pair<long long,int> 
using namespace std;
const int maxn=5e5+5;
const long long inf=1e18;
int n,k,a[maxn],b[maxn],cnt=1;long long ans;
auto un(pli x,pli y){return tuple{x.first+y.first,x.second,y.second};}
struct nod{
    int mn,ls,rs,ad;
    pli x={inf,0},y={inf,0},lx={inf,0},ry={inf,0};//x、y：最优左右括号，lx、ry：最优合法左右括号
    tuple<long long,int,int> fw={inf,0,0},bk={inf,0,0},rv={inf,0,0};//fw：直接贪心配对的最小花费，bk：合法反悔（不跨最低点）的最小花费；rv：跨越最低点、暂时不合法的反悔花费。
}tr[4*maxn];
void pd(int p){
    if(!tp.ls)tp.ls=++cnt;
    if(!tp.rs)tp.rs=++cnt;
    tr[tp.ls].mn+=tp.ad,tr[tp.rs].mn+=tp.ad;
    tr[tp.ls].ad+=tp.ad,tr[tp.rs].ad+=tp.ad;
    tp.ad=0;
}
void pu(int p){
    tp.mn=min(tr[tp.ls].mn,tr[tp.rs].mn);
    tp.x=min(tr[tp.ls].x,tr[tp.rs].x),tp.y=min(tr[tp.ls].y,tr[tp.rs].y);
    tp.fw=min(tr[tp.ls].fw,tr[tp.rs].fw);
    tp.fw=min(tp.fw,un(tr[tp.ls].x,tr[tp.rs].y));
    tp.bk=min(tr[tp.ls].bk,tr[tp.rs].bk);
    tp.rv=min({tr[tp.ls].rv,tr[tp.rs].rv,un(tr[tp.rs].x,tr[tp.ls].y)});
    if(tr[tp.ls].mn<tr[tp.rs].mn){
        tp.lx=tr[tp.ls].lx;
        tp.ry=min(tr[tp.ls].ry,tr[tp.rs].y);
        tp.bk=min({tp.bk,tr[tp.rs].rv,un(tr[tp.rs].x,tr[tp.ls].ry)});
    }else if(tr[tp.ls].mn>tr[tp.rs].mn){
        tp.lx=min(tr[tp.ls].x,tr[tp.rs].lx);
        tp.ry=tr[tp.rs].ry;
        tp.bk=min({tp.bk,tr[tp.ls].rv,un(tr[tp.rs].lx,tr[tp.ls].y)});
    }else{
        tp.lx=tr[tp.ls].lx;
        tp.ry=tr[tp.rs].ry;
        tp.bk=min(tp.bk,un(tr[tp.rs].lx,tr[tp.ls].ry));
    }
}
void ad(int l,int r,int x,int s,int t,int p){
    if(l<=s&&t<=r){
        tp.ad+=x,tp.mn+=x;
        return;
    }
    pd(p);
    int m=s+((t-s)>>1);
    if(l<=m)ad(l,r,x,s,m,tp.ls);
    if(m<r)ad(l,r,x,m+1,t,tp.rs);
    pu(p);
}
void upd(int x,long long k,bool xy,int s,int t,int p){
    if(s==t){
        if(xy)tp.x={k,s},tp.lx={k,s};
        else tp.y={k,s},tp.ry={inf,0};
        tp.fw=un(tp.x,tp.y),tp.bk={inf,0,0},tp.rv={inf,0,0}; 
        return;
    }
    pd(p);
    int m=s+((t-s)>>1);
    if(x<=m)upd(x,k,xy,s,m,tp.ls);
    else upd(x,k,xy,m+1,t,tp.rs);
    pu(p);
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],upd(i,a[i],1,1,n,1);
    for(int i=1;i<=n;i++)cin>>b[i],upd(i,b[i],0,1,n,1);
    for(int i=1;i<=k;i++){
        auto [fw,mi,mj]=min(tr[1].fw,tr[1].bk);
        ans+=fw;
        if(mi<mj)ad(mi,mj-1,1,1,n,1);
        else if(mi>mj)ad(mj,mi-1,-1,1,n,1);
        upd(mi,inf,1,1,n,1),upd(mj,inf,0,1,n,1);
    }
    cout<<ans;
    return 0;
}

::::

带限制生成树问题（破圈算法）

难度：蓝到紫 | 时间复杂度：O(m\log m+k\cdot V)

先求出最小生成树，为了满足要求，连上满足要求的最优边，此时会形成一个环，将环上最差的边删去。这就是破圈算法，正好对应之前说的不增加选择数目的反悔（树的边数不能变，所以为了满足要求，+1 的同时必须 -1）。

题目：

P5633 给定带权无向图，求得一棵生成树，满足节点 u 正好连了 k 条边，求最小边权和。

P4180 给定带权无向图，求严格次小生成树。

解法：

P5633：

存在更简单的 WQS 二分做法，但是反悔贪心对新手更友好。

由于对 u 的要求太特殊了，先不考虑 u，断开它的连边，用 Kruskal 求出其它块的最小生成树。然后再把每个块到 u 的最短边连起来（无解情况即没有边，或者块的数量大于要求边数）。

懂费用流的看到这个就会说：这不就是 EK 算法吗？实际上，如果抛弃“流量、容量、残余网络”这些死板的词汇，直接从纯粹的反悔贪心思维出发，代码的长度能缩短一半，常数也会更加优异。

先看一下建立反向负权边的用处，说一个简单的有向图：S \to A \to T,S \to B \to T,A \to B。现在想从 S 走到 T。如果我们找到第一条路径 S \to A \to B \to T，我们给经过的三条边建立反向负权边，下一次我们找到了 S \to B \to A \to T，我们不难发现，中间的 A \to B 其实等于没走，等同于走的是 S \to A \to T 和 S \to B \to T 两条路，这个反向负权边就像可以反悔一样，可以“改变”上一次走的路线。

更本质一点：按照之前的思维“如何让路径数 +1？”，贪心的方案就是，走一条与之前的边不相交的路（因为题目中的边权代表收益，不能重复拿）。

反悔呢？我们建立了反向负权边，反悔就是让旧的路少掉一段，换成一段新的路和另一条不相交的路。所以思维一直是没变的，反向负权边就是可以让之前的旧路可以被反悔的一种方式。

题目：

P2045 正方形矩阵，每一格有一个整数，从左上角走到右下角（只能向下和向右），问走 k 次所达到的方格的数的和的最大值。

P3356 网格图，有平地格，样本格，障碍格。障碍不能走，每个样本只能采集一次。从左上角走到右下角（只能向下和向右），问走 k 次使得采集样本数最多的方案。

P4012 网格图，每条边有边权。多个起点和终点，每个起点有出发机器人数，每个终点有到达机器人数限制。只能向下和向右，走过的边权清零，问所有机器人从起点走到终点的路径边权和的最大值。

解法：

几道题非常像，直接一起讲。

前两题建图发现是点权，拆点把点权改成边权（拆成入点和出点，中间连权值边）。

第三题学过 SPFA 可以想到建立虚拟的超级起点和超级终点，分别向网格起点和网格终点连对应数量的边。

三道题一样的部分：SPFA 跑最长路，建立反向负权边（记录前驱节点，一路回溯，删掉正向边，改建负权的反向边），除此之外一开始建图还需要一条权值为 0 的“过路边”（只经过，没收益）。一共跑 k 次，记录前驱节点。

同时在网格图中，可以从左到右从上到下给节点编号，这样就能通过点的差值判断关系，邻接表存图即可，不需要复杂的链式前向星。这也是纯反悔贪心思维的优势。

::::success[P3356 代码] 作者写的代码可能也一般般，更多写法请看题解区。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2*35*35+10;
int n,m,k,rcnt[maxn],dcnt[maxn],a[maxn];
vector<pair<int,int>> ed[maxn];
auto in=[](int i,int j){return i*m+j;};
auto out=[](int i,int j){return (n+i)*m+j;};//编号函数
bool spfa(){
    int dis[maxn],vis[maxn]={0},pre[maxn];
    fill(dis,dis+maxn,-1e9);
    queue<int> q;
    dis[0]=0,vis[0]=1;
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop(),vis[u]=0;
        for(auto [v,w]:ed[u]){
            if(dis[v]<dis[u]+w){
                dis[v]=dis[u]+w,pre[v]=u;
                if(!vis[v])q.push(v),vis[v]=1;
            }
        }
    }
    if(dis[out(n-1,m-1)]==-1e9)return 0; 
    auto gt=[&](int u,int v,int w){return find(ed[u].begin(),ed[u].end(),pair{v,w});};
    auto del=[&](int u,int v,int w){ 
        auto e=gt(u,v,w);
        *e=move(ed[u].back()),ed[u].pop_back();
    };//找边和删边的函数
    for(int p=out(n-1,m-1);p;p=pre[p]){
        int pr=pre[p],w=dis[p]-dis[pr];
        if(abs(p-pr)==n*m){//利用差值判断关系
            if(w)del(pr,p,w),ed[p].emplace_back(pr,-w);
            else if(pr<p)ed[p].emplace_back(pr,0);
            else del(pr,p,0);
        }else{
            bool fw=(pr>p); 
            int u=max(pr,p)-n*m,v=min(pr,p);
            (v-u==m?rcnt[u]:dcnt[u])+=(fw?1:-1); 
            if(fw)ed[p].emplace_back(pr,0);
            else del(pr,p,0);
        }
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>k>>n>>m;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            int u=in(j,i),v=out(j,i);
            cin>>a[u];
            if(a[u]==1)continue;
            if(a[u]==2)ed[u].emplace_back(v,1);
            ed[u].emplace_back(v,0);
            if(j&&a[in(j-1,i)]!=1)ed[out(j-1,i)].emplace_back(u,0);
            if(i&&a[in(j,i-1)]!=1)ed[out(j,i-1)].emplace_back(u,0);
        }
    }
    int cnt=0;
    while(k--&&spfa())cnt++;
    for(int i=1;i<=cnt;i++){
        int p=0;
        while(p!=in(n-1,m-1)){
            if(rcnt[p]>0){
                rcnt[p]--,p+=m;
                cout<<i<<" 1\n";
            }else{
                dcnt[p]--,p++;
                cout<<i<<" 0\n";
            }
        }
    }
    return 0;
}

实战技巧：搜打撤

说了这么多，读者可能遇到一道新题还是想不出，或者不会判断正确性。简单说一下面对不一定是反悔贪心的新题目，如何确定并想出正解？其实就是三个字：搜打撤。

搜： 审题寻找特征，不要急着开始写，要想明白题目是否符合“凸性”。有凸性没冲突是普通贪心，如果有了冲突（占空间、不相邻等）就说明需要反悔贪心出手了。

凸性究竟是啥？

主要是两种情况：收益递减和代价递增。

收益递减：每次 +1 的增加收益（例如得分）绝对不超过上一次的增加收益。

代价递增：每次 +1 的增加代价（例如空间占用）绝对不比上一次的少。

没有凸性时，收益可能先低后暴涨，贪心每次只能看见眼前那一步，必然漏解。

打： 用最自然、最暴力的贪心打出第一步。

很多萌新卡住，是因为一开始就试图同时兼顾“选物品”和“处理冲突”。正确的做法是先无视限制，想出理想情况的收益（选一个数）或代价（容量变少）是多少。

撤： 如果“打”不行了，就要考虑撤。反悔本质上就是给过去的决策买一份“后悔药”。两种反悔方式（一换一和退一选二）中选择合适的。把贪心收益和反悔收益要放入同一容器，选最优的执行。同时还要选择合适的数据结构维护：纯数值用堆，位置信息用链表，区间信息用线段树。

搜确认能贪，打算出增量，撤把冲突变成另一种增量。三者结合就是一个正确的反悔贪心。

总结：

反悔贪心这个分类，说广不广，说窄也不窄。狭义的反悔贪心或许只是一种特定的优先队列技巧，但是反悔贪心的思想铸就了更伟大的费用流体系。这种算法思维门槛确实不低，不经过刻意练习考场很难熟练做出。

CCF 近年来出的反悔贪心也越来越多了，序列、社团招新、糖果店都是反悔贪心好题，希望这篇文章，能给在学习这个算法的萌新拨开云雾、重见晴空，少背一点死板的模板，多多体会思维之美——也是信息学奥赛真正追求的。

代码全靠手写，制作不易。感谢大家的支持。