BZOJ3532【SDOI2014】LIS <网络流>

Posted on Symbols count in article: 1.3k Reading time ≈ 5 mins.

Problem

【SDOI2014】LIS

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}

Description

给定序列AA，序列中的每一项AiA_i有删除代价BiB_i和附加属性CiC_i。
请删除若干项，使得AA的最长上升子序列长度减少至少11，且付出的代价之和最小，并输出方案。
如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

Input

输入包含多组数据。
输入的第一行包含整数TT，表示数据组数。
接下来4×T4\times T行描述每组数据。
每组数据的第一行包含一个整数NN，表示AA的项数。
接下来三行，每行NN个整数A1∼AnA_1\sim A_n，B1∼BnB_1\sim B_n，C1∼CnC_1\sim C_n。

Output

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

Sample Input

1
2
3
4
5
1
6
3 4 4 2 2 3
2 1 1 1 1 2
6 5 4 3 2 1

Sample Output

1
2
4 3
2 3 6

Explanation

删去{A2,A,A6}\lbrace A_2,A_,A_6\rbrace,{A1,A6}\lbrace A_1,A_6\rbrace,{A2,A3,A4,A5}\lbrace A_2,A_3,A_4,A_5\rbrace等都是合法的方案，但{A2,A3,A6}\lbrace A_2,A_3,A_6\rbrace对应的CC值的字典序最小。

HINT

T≤5,1≤N≤700T\le 5, 1\le N\le 700
1≤Ai,Bi,Ci≤1091\le A_i,B_i,C_i\le 10^9，CiC_i两两不同

标签：网络流 退流

Solution

最小割+网络流退流

首先做一遍DP\mathrm{DP}求出ff数组，即每个前缀中的LIS\mathrm{LIS}长度，令最长的LIS\mathrm{LIS}长度为maxlenmaxlen。

若不考虑字典序最小的限制，只要求最小代价，则是一个最小割模型。将每个位置ii拆成i1i_1和i2i_2两个点，分别代表入点和出点。连接i1→i2i_1\to i_2流量BiB_i，割这条边代表删除ii。对于所有j<i,A[j]<A[i],f[i]=f[j]+1j<i,A[j]<A[i],f[i] = f[j]+1，连接j2→i1j_2\to i_1流量∞\infty，这样每个长度为maxlenmaxlen的序列都连成一条链，两位置间不能隔开，只能删除其中的某个数，即每个位置入点到出点的边。这样跑最大流得到最小割即为最小代价。

考虑字典序最小的限制。先用上面的建图跑出一个可行解，然后按CC从小往大看能否用CC小的数换当前可行解中CC大的数，显然每次还完之后要调整当前可行解。对于当前枚举到的位置ii，若其不在当前可行解中，则以i1i_1为源点，原源点ss为汇点，跑一遍网络流，再以TT为源点，i2i_2为汇点跑一遍网络流。这样可以用反向边使前面的可行流“返回”，达到调整可行解的效果。然后将i1→i2i_1\to i_2这条边删除，以后的可行解中将不再会删掉这个点。这样贪心调整即可得到最终答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define MAX_N 1500
#define MAX_M 2000000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, A[MAX_N+5], B[MAX_N+5], C[MAX_N+5];
int f[MAX_N+5], ord[MAX_N+5], ans[MAX_N+5];
int S, T, s, t, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
bool cmp (const int &x, const int &y) {return C[x] < C[y];}
struct node {int v, c, nxt;} E[MAX_M+5];
void init() {S = 0, T = 2*n+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que; que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow; int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = S; i <= T; i++) cr[i] = pr[i];}
void rec() {for (int i = S; i <= T; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0; cpy(); while (BFS()) ret += DFS(s, INF), rec(); return ret;}
int main() {
    int CASE; read(CASE);
    for (; CASE; puts(""), CASE--) {
        read(n), init(); int mx = 0, tot = 0;
        for (int i = 1; i <= n; i++) read(A[i]);
        for (int i = 1; i <= n; i++) read(B[i]);
        for (int i = 1; i <= n; i++) read(C[i]);
        for (int i = 1; i <= n; i++) ord[i] = i;
        for (int i = 1; i <= n; i++) f[i] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < i; mx = max(mx, f[j++]))
                if (A[j] < A[i]) f[i] = max(f[i], f[j]+1);
        for (int i = 1; i <= n; i++) addedge(i, i+n, B[i]);
        for (int i = 1; i <= n; i++)
            if (f[i] == 1) addedge(S, i, INF);
            else if (f[i] == mx) addedge(i+n, T, INF);
        for (int i = 1; i <= n; i++)
            for (int j = i+1; j <= n; j++)
                if (A[i] < A[j] && f[j] == f[i]+1)
                    addedge(i+n, j, INF);
        s = S, t = T, printf("%d ", Dinic());
        sort(ord+1, ord+n+1, cmp), s = ord[1], t = s+n;
        for (int i = 1; i <= n; s = ord[++i], t = s+n) if (!BFS())
            ans[++tot] = ord[i], 
            s = ord[i], t = S, Dinic(), 
            s = T, t = ord[i]+n, Dinic(), 
            E[ord[i]*2-2].c = E[ord[i]*2-1].c = 0;
        sort(ans+1, ans+tot+1), printf("%d\n", tot);
        for (int i = 1; i <= tot; i++) printf("%d ", ans[i]);
    }
    return 0;
}