题意：
分析：
首先，我们把问题拆开来考虑
-
删掉一些项使得最长上升子序列变短，那么删掉的项一定在原来最长的 (LIS) 里面，删掉某些东西的最小代价让我们很容易想到最小割，最小代价就可以求出来了，第一问解决
-
求一组方案使得字典序最小，求出所有的方案再找字典序最小的那一种显然复杂度不对劲，那我们只能构造字典序最小的那一组，然后判断是否可行，也就是说我们要判断一条边是否是一条可行边，也就是是否属于一个最小割，这就是一个经典问题呀（具体题目可以参考 AHOI Mincut )
- 对于最小割的可行边和必经边 (u o v) ,都满足这条边满流， (u o v) 不存在新的增广路径，但是必须边还满足 残量网络中，u,v 不属于同一个 SCC
放到这个题上来说就是，我们按照 (c) 从小到大枚举边，判断它是否是可行边，如果是，为了防止它对其他边选择的影响，反着跑 dinic 退流，具体来说就是原来是 (s o in(e)) 有一些流量，那么现在就从 (in(e) o s)) 增广，把原来加的流量都删掉，使得原来一些满流的边不在满流，然后把枚举的这条边的流量置为 (0)，还是不影响它作为最小割边集里的一条边的性质
tip:
按照讨论区的反馈和自身经历，这题有些卡常，每次都是 (1.05s) 最后手写队列提到了 (0.6) 秒左右
代码：
#include<bits/stdc++.h>
#define in(rt) rt<<1
#define out(rt) rt<<1|1
#define reg register
#define inl inline
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 1505;
const int maxm = 1e6+5;
const int inf = 0x3f3f3f3f;
int ti,n,m,cnt,num,S,T,l,r;
int dp[maxn],dep[maxn<<1],cur[maxn<<1],head[maxn<<1],ans[maxn],pos[maxn],qu[maxn];
struct node
{
int a,b,c,id;
bool operator <(const node &b)const
{
return c<b.c;
}
}t[maxn];
struct edge
{
int to,nxt,w;
}e[maxm];
inl void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inl void add_edge(int u,int v,int w)
{
add(u,v,w);add(v,u,0);
}
bool bfs(int st,int ed)
{
for(int i=0;i<=(n<<1)+2;i++) dep[i]=-1,cur[i]=head[i];
l=r=0;
qu[r++]=st;
dep[st]=0;
while(l<r)
{
int u=qu[l++];
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].w&&dep[v]==-1)
{
dep[v]=dep[u]+1;
if(v==ed) return true;
qu[r++]=v;
}
}
}
return dep[ed]!=-1;
}
int dfs(int u,int flow,int ed)
{
if(u==ed) return flow;
int used=0,w;
for(int &i=cur[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(e[i].w&&dep[v]==dep[u]+1)
{
w=dfs(v,min(e[i].w,flow-used),ed);
e[i].w-=w;
e[i^1].w+=w;
used+=w;
if(used==flow) return flow;
}
}
if(!used) dep[u]=-1;
return used;
}
inl int dinic(int st,int ed)
{
int res=0;
while(bfs(st,ed)) res+=dfs(st,inf,ed);
return res;
}
void work()
{
ti=read();
while(ti--)
{
n=read();cnt=1;S=0;T=(n<<1)+2;num=m=0;
for(reg int i=1;i<=n;i++) t[i].a=read(),t[i].id=i;
for(reg int i=1;i<=n;i++) t[i].b=read();
for(reg int i=1;i<=n;i++) t[i].c=read();
for(reg int i=1;i<=n;i++)
{
dp[i]=1;
for(reg int j=1;j<i;j++)
{
if(t[i].a>t[j].a) dp[i]=max(dp[i],dp[j]+1);
}
m=max(m,dp[i]);
}
for(reg int i=1;i<=n;i++)
{
add_edge(in(i),out(i),t[i].b);pos[i]=cnt;
if(dp[i]==1) add_edge(S,in(i),inf);
else if(dp[i]==m) add_edge(out(i),T,inf);
for(reg int j=i+1;j<=n;j++) if(dp[j]==dp[i]+1&&t[j].a>t[i].a) add_edge(out(i),in(j),inf);
}
printf("%d ",dinic(S,T));
sort(t+1,t+n+1);
for(reg int i=1;i<=n;i++)
{
int id=t[i].id;
if(!bfs(in(id),out(id)))
{
ans[++num]=id;
while(bfs(T,out(id))) dfs(T,inf,out(id));
while(bfs(in(id),S)) dfs(in(id),inf,S);
e[pos[id]].w=e[pos[id]^1].w=0;
}
}
printf("%d
",num);
sort(ans+1,ans+num+1);
for(reg int i=1;i<=num;i++) printf("%d ",ans[i]);
puts("");
for(reg int i=0;i<=T;i++) head[i]=0;
}
}
}
int main()
{
zzc::work();
return 0;
}