【题意】
【分析】
LIS部分和网络流24题中的P2766 最长不下降子序列问题一致
主要是多了一个输出方案,这个就需要用到贪心退流的方式了
【代码】
#include<bits/stdc++.h> using namespace std; #define INF 1e9 const int M=1000000; const int N=1500; int tot,nxt[M],point[N],remind[M],v[M],dis[N],cur[N],n,a[N],b[N],f[N],ans[N]; struct hh{int c,bh,x;}li[N]; int read() { int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9' && ch>='0') x=x*10+ch-'0',ch=getchar(); return x; } void addline(int x,int y,int z) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remind[tot]=z; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remind[tot]=0; } bool bfs(int s,int t) { for (int i=0;i<=n*2+1;i++) cur[i]=point[i]; queue<int>q;q.push(s); memset(dis,0x7f,sizeof(dis));dis[s]=0; while (!q.empty()) { int now=q.front();q.pop(); for (int i=point[now];i!=-1;i=nxt[i]) if (dis[v[i]]>INF && remind[i]) { dis[v[i]]=dis[now]+1; q.push(v[i]); if (dis[t]<INF) return 1; } } return 0; } int dfs(int now,int t,int limit) { if (now==t || !limit) return limit; int flow=0,f; for (int i=cur[now];i!=-1;i=nxt[i]) { cur[now]=i; if (remind[i] && dis[v[i]]==dis[now]+1) { f=dfs(v[i],t,min(limit,remind[i])); limit-=f; flow+=f; remind[i]-=f; remind[i^1]+=f; if (!limit) return flow; } } return flow; } int dinic(int s,int t) { int ans=0; while (bfs(s,t)) ans+=dfs(s,t,INF); return ans; } int cmp(hh a,hh b){return a.c<b.c;} int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); int T;T=read(); while (T--) { tot=-1;memset(point,-1,sizeof(point)); n=read();int len=0; 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++) li[i].c=read(),li[i].x=i; for (int i=1;i<=n;i++) { int maxx=0; for (int j=1;j<i;j++) if (a[j]<a[i] && f[maxx]<f[j]) maxx=j; f[i]=f[maxx]+1; len=max(len,f[i]); } int s=0,t=n*2+1; for (int i=1;i<=n;i++) { li[i].bh=tot+1,addline(i,i+n,b[i]); if (f[i]==1) addline(s,i,INF); else if (f[i]==len) addline(i+n,t,INF); for (int j=i+1;j<=n;j++) if (a[j]>a[i] && f[j]==f[i]+1) addline(i+n,j,INF); } int m=dinic(s,t),num=0; printf("%d ",m); sort(li+1,li+n+1,cmp); for (int i=1;i<=n;i++) { if (bfs(li[i].x,li[i].x+n)) continue; dinic(t,li[i].x+n); dinic(li[i].x,s); ans[++num]=li[i].x; remind[li[i].bh]=remind[li[i].bh^1]=0; } sort(ans+1,ans+num+1);printf("%d\n%d",num,ans[1]); for (int i=2;i<=num;i++) printf(" %d",ans[i]); printf("\n"); } }