3532: [Sdoi2014]Lis

3532: [Sdoi2014]Lis

链接

分析：

　　首先dp一遍，求出f[i]，表示第i个位置在最长上升子序列中的最优排在什么位置。

　　然后建图，求最小割，可以求得第一问。S->i，容量INF；i->i+n，容量B[i]；i+n->T，容量INF。

　　对于求字典序最小的最小割，那么首先按C排序，依次判断每条边是否可以存在于最小割中。

　　判断条件：对于u->v，满足这条边满流，并且u到v不能再增广了。

　　之后要消掉这条边的影响，需要用到退流，即从u向S，T向v+n跑一遍最大流。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 2005, INF = 1e9;
struct Edge { int to, nxt, cap; } e[600005];
struct Node { int c, id; } C[N];
int head[N], dis[N], q[N], cur[N], A[N], B[N], f[N], id[N], En = 1, n;
vector<int> ans;

bool cmp(const Node &A,const Node &B) { return A.c < B.c; }
inline void add_edge(int u,int v,int w) {
    ++En; e[En].to = v, e[En].cap = w, e[En].nxt = head[u]; head[u] = En;
    ++En; e[En].to = u, e[En].cap = 0, e[En].nxt = head[v]; head[v] = En;
}
bool bfs(int S,int T) {
    for (int i = 0; i <= n + n + 1; ++i) dis[i] = -1, cur[i] = head[i];
    int L = 1, R = 0; q[++R] = S; dis[S] = 0;
    while (L <= R) {
        int u = q[L ++];
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[v] == -1 && e[i].cap > 0) {
                dis[v] = dis[u] + 1;
                q[++R] = v;
                if (v == T) return true;
            }
        }
    }
    return false;    
}
int dfs(int u,int T,int flow) {
    if (u == T) return flow;
    int used = 0;
    for (int &i = cur[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (dis[v] == dis[u] + 1 && e[i].cap > 0) {
            int tmp = dfs(v, T, min(flow - used, e[i].cap));
            if (tmp > 0) {
                e[i].cap -= tmp, e[i ^ 1].cap += tmp;
                used += tmp;
                if (used == flow) break;
            }
        }
    }
    if (used != flow) dis[u] = -1;
    return used;
}
int dinic(int S,int T) {
    int ans = 0;
    while (bfs(S, T)) ans += dfs(S, T, INF);
    return ans;
}
bool check(int x) {
    return (!(e[id[x]].cap||bfs(x,x+n)));
    return e[id[x]].cap == 0 && !bfs(x, x + n);
}
void solve() {
    n = read();
    for (int i = 1; i <= n; ++i) A[i] = read();
    for (int i = 1; i <= n; ++i) B[i] = read();
    for (int i = 1; i <= n; ++i) C[i].c = read(), C[i].id = i;
    sort(C + 1, C + n + 1, cmp);
    int S = 0, T = n + n + 1, len = 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);
        len = max(len, f[i]);
    }
    for (int i = 1; i <= n; ++i) {
        if (f[i] == 1) add_edge(S, i, INF);
        else if (f[i] == len) add_edge(i + n, T, INF);
        for (int j = i + 1; j <= n; ++j) 
            if (A[j] > A[i] && f[j] == f[i] + 1) 
                add_edge(i + n, j, INF);
        add_edge(i, i + n, B[i]); 
        id[i] = En - 1;
    }
    printf("%d ", dinic(S, T));
    for (int i = 1; i <= n; ++i) {
        int x = C[i].id;
        if (!check(x)) continue;
        ans.push_back(x);
        dinic(x, S);
        dinic(T, x + n);
        e[id[x]].cap = e[id[x] + 1].cap = 0;
    }
    sort(ans.begin(), ans.end());
    printf("%d
", ans.size());
    for (int i = 0; i < (int)ans.size(); ++i) printf("%d ",ans[i]);puts("");
    En = 1, memset(head, 0, sizeof(head));
    ans.clear();
}
int main() {
    for (int T = read(); T--; ) solve();
    return 0;
}