题意

给出\(n\)个三元组\(a_i,b_i,c_i\),要求删除一些三元组,使得\(a_i\)的 LIS 至少 \(-1\) ,\(b_i\)的代价最小,在这个情况下要求\(c_i\)的字典序最小。

分析

考虑 LIS 的转移公式 \(f[i]=max_{j<i,a_j<a_i}f[j]+1\),也就是这样的\(j\)会对\(i\)有制约。于是我们考虑建图:

  • 每个位置拆成两个结点,一个为入点,一个为出点,入点向出点连一条边,代价为\(b_i\)
  • 对于满足上述关系\(f[i]=max_{j<i,a_j<a_i}f[j]+1\)的关系\((j,i)\),\(j\)向\(i\)连一条边,代价为\(INF\)
  • 源点向所有满足\(f[i]=1\)的点的入点连边
  • 所有满足\(f[i]=MAX\)的点的出点向汇点连边

显然,这样的情况下,最小割就是答案。

考虑输出方案。我们要寻找割边。

如果一条边是割边,显然满足,这条边在所有的最大流中均满流,如何判断它呢,我们只需要判断它是否在残余网络中流通即可。

这样以来,我们对于\(c_i\)排序以后,贪心的选取割边。

如果当前的边是割边,我们在网络中删去这条边(退流),然后继续按照字典序寻找割边。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注