题目大意：给定序列$A$，序列中的每一项$A_i$有删除代价$B_i$和附加属性$C_i$。请删除若干项，使得$A$的最长上升子序列长度至少减少$1$，且代价最小，并输出方案。若有多种方案，$C$的字典序最小的一种。
题解：如果只要求输出代价，令$f_i$表示到$i$的最长上升子序列长度，把所有$j<i\&\&a_j<a_i\&\&f_i=f_j+1$的$i$和$j$之间连一条边，跑一遍最小割就行了。
但是题目要求字典序最小，可以贪心，按$C$从小到大排序，每次看一条边是否可能是最小割中的边，是的话就删去。
那么就要求较快出一条边是否可以在最小割中。
比如求$(u,v)$是否是可以在最小割中，正常的方法是把这条边的容量减$1$，看最小割的大小是不是减少$1$。但这样很慢，这可以转变为在残量网络上看从$u$出发是否能找到一条$u$到$v$的增广路，如果找不到就说明该边可能在最小割中。
发现，删去一条边后，需要重新计算最大值。
这时可以使用退流，比如把$(u,v)$退流，就可以在残量网络中跑两遍最大流，分别是$(u,start)$和$(end,v)$，这样就可以把这条边的流量的贡献减去
卡点：1.$f$数组没清空
C++ Code：
#include#include #include //#define int long long#define maxn 1410#define maxm 246000#define X(x) ((x << 1) - 1)#define Y(x) (x << 1)using namespace std;const long long inf = 0x3f3f3f3f3f3f3f3f;int Tim, n;int A[maxn], C[maxn], rnk[maxn], num[maxn];int ans[maxn], ansn;long long B[maxn];int f[maxn], maxf = 0;int head[maxn], cnt = 2;struct Edge { int to, nxt; long long w;} e[maxm << 1];void add(int a, int b, long long c) { e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt; e[cnt ^ 1] = (Edge) {a, head[b], 0}; head[b] = cnt ^ 1; cnt += 2;}inline int max(int a, int b) {return a > b ? a : b;}inline long long min(long long a, long long b) {return a < b ? a : b;}inline bool cmp(int a, int b) {return C[a] < C[b];}int st, ed, tst, ted;int d[maxn];int q[maxn], h, t;bool bfs() { memset(d, 0, sizeof d); d[q[h = t = 0] = tst] = 1; while (h <= t) { int u = q[h++]; if (u == ted) return true; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (e[i].w && !d[v]) { d[v] = d[u] + 1; q[++t] = v; } } } return d[ted];}long long dfs(int x, long long low) {// printf("in:%d %lld\n", x, low); if (!low || x == ted) return low;// printf("no:%d %lld\n", x, low); int v; long long res = 0, w; for (int i = head[x]; i; i = e[i].nxt) { v = e[i].to; if (e[i].w && d[v] == d[x] + 1) { w = dfs(v, min(low - res, e[i].w)); e[i].w -= w; e[i ^ 1].w += w; res += w; if (low == res) return low; } }// printf("out:%d %lld\n", x, res); if (!res) d[x] = -1; return res;}long long dinic(int st, int ed) { tst = st, ted = ed; long long ans = 0; while (bfs()) ans += dfs(tst, inf); return ans;}signed main() { scanf("%d", &Tim); while (Tim --> 0) { scanf("%d", &n); st = 0, ed = n << 1 | 1; for (int i = 1; i <= n; i++) scanf("%d", &A[i]); for (int i = 1; i <= n; i++) scanf("%lld", &B[i]); for (int i = 1; i <= n; i++) scanf("%d", &C[i]), rnk[i] = i; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) if (A[j] < A[i]) f[i] = max(f[i], f[j] + 1);// printf("%d %d\n", i, f[i]); maxf = max(maxf, f[i]); }// printf("lalal:%d\n", maxf); for (int i = 1; i <= n; i++) { num[i] = cnt; add(X(i), Y(i), B[i]); if (f[i] == 1) add(st, X(i), inf); if (f[i] == maxf) add(Y(i), ed, inf); for (int j = i + 1; j <= n; j++) { if (A[i] < A[j] && f[i] + 1 == f[j]) add(Y(i), X(j), inf); } } printf("%lld ", dinic(st, ed)); ansn = 0; sort(rnk + 1, rnk + n + 1, cmp); for (int i = 1; i <= n; i++) { int now = rnk[i], E = num[now];// printf("%d %lld\n", now, e[E].w); if (!e[E].w) { tst = X(now), ted = Y(now); if (!bfs()) { dinic(ed, Y(now)); dinic(X(now), st); e[E].w = e[E ^ 1].w = 0; ans[++ansn] = now; } } } sort(ans + 1, ans + ansn + 1); printf("%d\n", ansn); for (int i = 1; i < ansn; i++) printf("%d ", ans[i]); printf("%d\n", ans[ansn]); if (Tim) { cnt = 2; memset(f, 0, sizeof f); memset(head, 0, sizeof head); maxf = 0; } } return 0;}