BZOJ3532: [Sdoi2014]Lis

  1 /**************************************************************
  2     Problem: 3532
  3     User: zhuohan123
  4     Language: C++
  5     Result: Accepted
  6     Time:9472 ms
  7     Memory:18660 kb
  8 ****************************************************************/
  9  
 10 #include <iostream>
 11 #include <cstdio>
 12 #include <cstring>
 13 #include <algorithm>
 14 using namespace std;
 15 typedef long long LL;
 16 const int maxpoint=11000,maxedge=1100000;
 17 const LL inf=~0ULL>>3;
 18 int head[maxpoint],nowhead[maxpoint],pointsize;
 19 struct edge{int to,next;LL c;}g[maxedge];int gnum=1;
 20 void addedge(int from,int to,LL c)
 21 {
 22     g[++gnum].to=to;g[gnum].c=c;g[gnum].next=head[from];head[from]=gnum;
 23     g[++gnum].to=from;g[gnum].c=0;g[gnum].next=head[to];head[to]=gnum;
 24 }
 25 int dfsstart,dfsend,dis[maxpoint];
 26 int q[maxpoint],ql,qr;
 27 bool BFS()
 28 {
 29     for(int i=1;i<=pointsize;i++)nowhead[i]=head[i],dis[i]=0;
 30     ql=1;qr=0;q[++qr]=dfsend;
 31     while(ql<=qr)
 32         for(int now=q[ql++],i=head[now];i;i=g[i].next)
 33         if(g[i^1].c&&!dis[g[i].to]&&g[i].to!=dfsend)
 34             dis[q[++qr]=g[i].to]=dis[now]+1;
 35     return dis[dfsstart];
 36 }
 37 LL DFS(int po,LL delta)
 38 {
 39     if(po==dfsend)return delta;
 40     LL nowans=0,tans;
 41     for(int&i=nowhead[po];i&&delta;i=g[i].next)
 42         if(g[i].c&&dis[g[i].to]+1==dis[po]&&(tans=DFS(g[i].to,min(delta,g[i].c))))
 43             g[i].c-=tans,g[i^1].c+=tans,nowans+=tans,delta-=tans;
 44     return nowans;
 45 }
 46 LL dinic(int start,int end)
 47 {
 48     dfsstart=start,dfsend=end;
 49     LL ans=0;
 50     while(BFS())ans+=DFS(start,inf);
 51     return ans;
 52 }
 53 int n;
 54 int a[1100],b[1100],f[1100];
 55 struct T
 56 {
 57     int num,pos;
 58     friend bool operator<(T A,T B){return A.num<B.num;}
 59 }c[1100];
 60 int oans[1100],ansnum;
 61 int main(int argc, char *argv[])
 62 {
 63     //freopen("1.in","r",stdin);
 64     //freopen("1.out","w",stdout);
 65     int Ti;scanf("%d",&Ti);
 66     while(Ti--)
 67     {
 68         memset(head,0,sizeof head);gnum=1;
 69         scanf("%d",&n);
 70         for(int i=1;i<=n;i++)scanf("%d",&a[i]);
 71         for(int i=1;i<=n;i++)scanf("%d",&b[i]);
 72         for(int i=1;i<=n;i++)scanf("%d",&c[i].num),c[i].pos=i;
 73         int maxf=0;
 74         for(int i=1;i<=n;i++)f[i]=1;
 75         for(int i=1;i<=n;i++)
 76             for(int j=1;j<i;j++)
 77                 if(a[j]<a[i])maxf=max(maxf,f[i]=max(f[i],f[j]+1));
 78         for(int i=1;i<=n;i++)
 79         {
 80             addedge(2*i+1,2*i+2,b[i]);
 81             if(f[i]==1)addedge(1,2*i+1,inf);
 82             if(f[i]==maxf)addedge(2*i+2,2,inf);
 83             for(int j=1;j<i;j++)
 84                 if(a[j]<a[i]&&(f[j]+1==f[i]))
 85                 addedge(2*j+2,2*i+1,inf);
 86         }
 87         pointsize=2*n+2;
 88         LL ans=dinic(1,2);
 89         sort(c+1,c+n+1);
 90         ansnum=0;
 91         for(int i=1;i<=n;i++)
 92         {
 93             int ne=0,po=c[i].pos;
 94             for(int j=head[2*po+1];j;j=g[j].next)
 95                 if(g[j].to==2*po+2){ne=j;break ;}
 96             if(g[ne].c==0)
 97             {
 98                 dfsstart=2*po+1,dfsend=2*po+2;
 99                 if(!BFS())
100                 {
101                     dinic(2,2*po+2);
102                     dinic(2*po+1,1);
103                     g[ne^1].c=0;
104                     oans[++ansnum]=po;
105                 }
106             }
107         }
108         sort(oans+1,oans+ansnum+1);
109         printf("%lld %d\n",ans,ansnum);
110         for(int i=1;i<ansnum;i++)printf("%d ",oans[i]);printf("%d\n",oans[ansnum]);
111          
112     }
113     return 0;
114 }