@loj - 2196@「SDOI2014」Lis

- 日理万妓 2023-06-01 13:59 14阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定序列 A，序列中的每一项 Ai 有删除代价 Bi 和附加属性 Ci

请删除若干项，使得 A 的最长上升子序列长度减少至少 1，且付出的代价之和最小，并输出方案。

如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

**输入格式**  
输入包含多组数据。  
输入的第一行包含整数 T，表示数据组数。  
接下来 4T 行描述每组数据：  
每组数据的第一行包含一个整数 N，表示 A 的项数，接下来三行，每行 N 个整数 A1, ..., AN; B1, ..., BN; C1, ..., CN。

**输出格式**  
对每组数据，输出两行。  
第一行包含两个整数 S，M，依次表示删去项的代价和与数量；  
接下来一行 M 个整数，表示删去项在 A 中的位置，按升序输出。

**样例**  
**样例输入**  
1  
6  
3 4 4 2 2 3  
2 1 1 1 1 2  
6 5 4 3 2 1  
**样例输出**  
4 3  
2 3 6

**数据范围与提示**  
对于所有的数据， 1 <= N <= 700, T <= 5, 1 <= Ai, Bi, Ci <= 10^9 且保证 Ci 两两不同。

## @solution@ ##

假如不考虑方案，我们可以先跑最长上升子序列的 dp，记录每个点为结尾的最长上升子序列 f\[x\]，并记录全局最优解 mx。  
然后考虑建一个分层图，其中 x 向 y 连边当且仅当 dp 时 x 能够作为 y 的最优决策点（即 x < y 且 A\[x\] < A\[y\] 且 f\[x\] + 1 = f\[y\]）。  
假如我选择一些点删掉，使得整张图没有点可以从 f\[x\] = 1 跑到 f\[x\] = mx，则原序列的最长上升子序列肯定长度减小。

于是我们考虑先将建出来的分层图拆点，然后建源点 s 连 f\[x\] = 1 的点，将 f\[x\] = mx 的点连向汇点 t，跑最小割即可得到答案。  
现在来考虑怎么求一个字典序最小的最小割方案。不难想到应该使用贪心的方法，按 Ci 从小到大依次取，并尝试将当前这个 i 加入最小割。

怎么判断一条边 i 是否可以在最小割内？最暴力的方法无疑是将这条边删掉，看最大流（即最小割）的变化量是否等于这条边的容量。  
等效替代一下，就是看这条边 (u, v) 是否能从 u 出发通过残余网络到达 v。

怎么消掉一条边的影响？最暴力的方法一样是将这条边删掉，然后重跑最大流。  
稍微快一些的方法是：跑 (t, v) 的最大流，跑 (u, s) 的最大流，跑最大流时限制总流量 = (u, v) 的流量，并把 (u, v) 这条边的容量与流量都设置为 0。  
这个操作称之为退流操作。

然而退流操作要常数小，有时候单路增广甚至要快一些（因为增广路本身不会太长），而多路增广需要重新给 n 个点求距离标号所以会大量访问到无用点。  
比较折中方法是在 dinic 求距离标号时一旦遇到终点就立刻返回进行增广。

## @accepted code@ ##

#include<cstdio> #include<vector> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int MAXN = 700; const int MAXV = 2*MAXN; const int MAXE = 3*MAXV*MAXV; const int INF = (1<<30); struct FlowGraph{ struct edge{ int to, cap, flow; edge *nxt, *rev; }edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt; int s, t, n; void clear(int _n) { n = _n; ecnt = &edges[0]; for(int i=0;i<=n;i++) adj[i] = NULL; } void addedge(int u, int v, int c) { edge *p = (++ecnt), *q = (++ecnt); p->to = v, p->cap = c, p->flow = 0; p->nxt = adj[u], adj[u] = p; q->to = u, q->cap = 0, q->flow = 0; q->nxt = adj[v], adj[v] = q; p->rev = q, q->rev = p; // printf("%d %d %lld\n", u, v, c); } queue<int>que; int d[MAXV + 5]; bool relabel() { for(int i=0;i<=n;i++) cur[i] = adj[i], d[i] = n + 5; while( !que.empty() ) que.pop(); d[t] = 0, que.push(t); while( !que.empty() ) { int f = que.front(); que.pop(); for(edge *p=adj[f];p;p=p->nxt) if( d[f] + 1 < d[p->to] && p->rev->cap > p->rev->flow ) { d[p->to] = d[f] + 1; que.push(p->to); if( p->to == s ) return true; } } return !(d[s] == n + 5); } int aug(int x, int tot) { if( x == t ) return tot; int sum = 0; for(edge *&p=cur[x];p;p=p->nxt) { if( p->cap > p->flow && d[p->to] + 1 == d[x] ) { int del = aug(p->to, min(p->cap - p->flow, tot - sum)); p->flow += del, p->rev->flow -= del, sum += del; if( sum == tot ) break; } } return sum; } int max_flow(int _s, int _t, int tot) { s = _s, t = _t; int flow = 0; while( tot && relabel() ) { int del = aug(s, tot); flow += del, tot -= del; } return flow; } }G; int A[MAXN + 5], f[MAXN + 5]; FlowGraph::edge *e[MAXN + 5]; pair<int, int>C[MAXN + 5]; int ans[MAXN + 5], cnt; void solve() { int N, s, t; scanf("%d", &N); s = 0, t = 2*N + 1, G.clear(t); for(int i=1;i<=N;i++) scanf("%d", &A[i]); int mx = 0; for(int i=1;i<=N;i++) { f[i] = 1; for(int j=1;j<i;j++) if( A[j] < A[i] ) f[i] = max(f[i], f[j] + 1); mx = max(mx, f[i]); } for(int i=1;i<=N;i++) { int x; scanf("%d", &x); G.addedge(i, i + N, x); e[i] = G.adj[i]; } for(int i=1;i<=N;i++) { if( f[i] == 1 ) G.addedge(s, i, INF); if( f[i] == mx ) G.addedge(i + N, t, INF); for(int j=1;j<i;j++) if( f[j] + 1 == f[i] ) G.addedge(j + N, i, INF); } for(int i=1;i<=N;i++) scanf("%d", &C[i].first), C[i].second = i; sort(C + 1, C + N + 1); printf("%d", G.max_flow(s, t, INF)); cnt = 0; for(int i=1;i<=N;i++) { int x = C[i].second; G.s = e[x]->rev->to, G.t = e[x]->to; if( !G.relabel() ) { G.max_flow(t, e[x]->to, e[x]->flow), G.max_flow(e[x]->rev->to, s, e[x]->flow); e[x]->cap = e[x]->flow = e[x]->rev->cap = e[x]->rev->flow = 0; ans[++cnt] = x; } } sort(ans + 1, ans + cnt + 1); printf(" %d\n", cnt); for(int i=1;i<=cnt;i++) printf("%d%c", ans[i], i == cnt ? '\n' : ' '); } int main() { int T; scanf("%d", &T); while( T-- ) solve(); }

## @details@ ##

woc 为什么我用 long long 就会多 TLE 一个点啊。。。

难道这个数据范围（指 Bi <= 10^9）不应该开 long long 吗。。。

为什么 int 能过啊。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11396826.html