P3308 [SDOI2014] LIS
大意
给定序列 \(A\)，序列中的每一项 \(A_i\) 有删除代价 \(B_i\) 和附加属性 \(C_i\)。请删除若干项，使得 \(A\) 的最长上升子序列长度减少至少 \(1\)，且付出的代价之和最小，并输出方案。
如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。
思路
首先，我们要考虑这个玩意的最小割，那么我们只需要在原序列上，跑一次最长上升子序列的 DP，然后根据 DP 的值，如果值为 \(1\) 就和 \(S\) 连一边，如果值为 \(len\) 就与 \(T\) 连一边，还有内部的上升规则，如果 \(p[i].a < p[j].a\) 且 \(dp[j] = dp[i] + 1\)，那么就连边。
建完图之后呢？直接跑最小割，然后就完了...吗？
我们发现我们求出的最小割并不定是字典序最小的那个，我们需要求的是有很多不同集的情况的最小割里面字典序最小的。
这个时候就需要用到退流的操作了，如果我们对于 \(u \to v\) 这条边进行退流，那么显然是从 \(u \to S\) 和 \(T \to v\) 进行退流，我们按照 \(c\) 的大小排序，检查其是否能构成最小割，然后进行删边退流，然后检查图的联通（这里不要偷懒，重新写个函数）。
在删边的过程中记录一下答案。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 705 * 2;
const int MAXM = MAXN * MAXN;
const int INF = 1e9;int S, T;
struct node{int a, b, c, id;
}p[MAXN];
struct NODE{int v, nxt, c;
}e[MAXM << 2];
int tot, h[MAXN], idx[MAXN], cur[MAXN];
int dp[MAXN], len = 0;
void init(){tot = 0;memset(h, -1, sizeof(h));
}
void add(int u, int v, int c){e[tot] = {v, h[u], c};h[u] = tot ++;e[tot] = {u, h[v], 0};h[v] = tot ++;
}int TT, n;
int d[MAXN];bool check(int s, int t){queue<int> q;static int vis[MAXN];memset(vis, 0, sizeof(vis));q.push(s);vis[s] = 1;while(!q.empty()){int u = q.front();q.pop();if(u == t) return true;for(int i = h[u];~i;i = e[i].nxt){if(e[i].c > 0 && !vis[e[i].v]){vis[e[i].v] = 1;q.push(e[i].v);}}}return false;
}bool bfs(int s, int t){queue<int> q;memset(d, -1, sizeof(d));q.push(s);d[s] = 0;while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(d[v] == -1 && e[i].c){d[v] = d[u] + 1;q.push(v);}}}return (d[t] != -1);
}int dfs(int s, int t, int flow){if(s == t || !flow){return flow;}int res = 0;for(int &i = cur[s];~i;i = e[i].nxt){int v = e[i].v;if(d[v] == d[s] + 1 && e[i].c){int tmp = dfs(v, t, min(flow, e[i].c));if(!tmp) continue;e[i].c -= tmp;e[i ^ 1].c += tmp;flow -= tmp;res += tmp;if(!flow) break;}}if(!res) d[s] = -1;return res;
}int Dinic(int s, int t){int res = 0;while(bfs(s, t)){memcpy(cur, h, sizeof(h));res += dfs(s, t, INF);}return res;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cin >> TT;while(TT --){init();cin >> n;S = 0, T = 2 * n + 1;for(int i = 1;i <= n;i ++){cin >> p[i].a;}for(int i = 1;i <= n;i ++){cin >> p[i].b;}for(int i = 1;i <= n;i ++){cin >> p[i].c;p[i].id = i;}len = 0;for(int i = 1;i <= n;i ++){dp[i] = 1;for(int j = 1;j < i;j ++){if(p[j].a < p[i].a){dp[i] = max(dp[i], dp[j] + 1);}}len = max(len, dp[i]);}for(int i = 1;i <= n;i ++){idx[i] = tot;add(i, i + n, p[i].b);if(dp[i] == 1){add(S, i, INF);}if(dp[i] == len){add(i + n, T, INF);}for(int j = 1;j < i;j ++){if(dp[i] == dp[j] + 1 && p[j].a < p[i].a){add(j + n, i, INF);}}}int max_flow = Dinic(S, T);sort(p + 1, p + n + 1, [](node x, node y){return x.c < y.c;});vector<int> ans;for(int i = 1;i <= n;i ++){int k = p[i].id;int u = k, v = k + n;if(check(u, v)) continue;ans.push_back(k);int flow = e[idx[k] ^ 1].c;e[idx[k]].c = e[idx[k] ^ 1].c = 0;if(flow > 0){while(bfs(u, S)){memcpy(cur, h, sizeof(h));int cnt = dfs(u, S, flow);}while(bfs(T, v)){memcpy(cur, h, sizeof(h));int cnt = dfs(T, v, flow);}}}sort(ans.begin(), ans.end());cout << max_flow << ' ' << ans.size() << '\n';for(int &x : ans){cout << x << ' ';}cout << '\n';}return 0;
}