（其实主要并不是写题解，只是记录一下网络流的一些……结论？）

1.「边u->v处于割集中」<=>「跑完最大流的残量网络上,u->v无路径」

（敲黑板划重点，不是u->v这条边为空就完事了，WA了好几次......）

（写网络流总是忘记反向边影响的我?‍♀️）

 

2.「割去割集中的u->v再跑网络流」即「跑T->v,u->S的最大流」

（考虑把v->u这条边变回u->v，再将其流量清空。）

 

总之，知道这两点这题就差不多了。

 

1 #include 
     
        2 using namespace std;  3   4 #define rep(i,l,r) for(int i=l;i<=r;++i)  5 #define per(i,r,l) for(int i=r;i>=l;--i)  6 #define pb push_back  7 #define mp make_pair  8   9 typedef long long ll; 10 typedef pair
      
        pii; 11  12 const int NN=707,N=1e5+3,M=1e6+3; 13 const ll INF=1e13; 14  15 int n,a[NN],b[NN],c[NN]; 16  17 int fst[N],nxt[M],to[M],len,S,T; 18 ll f[M]; 19 void ad(int u,int v,ll w){ 20     to[++len]=v;f[len]=w; 21     nxt[len]=fst[u];fst[u]=len; 22 } 23 void add(int u,int v,ll w){ 24     ad(u,v,w); 25     ad(v,u,0); 26 } 27  28 int bg,ed,oc[N],dep[N]; 29 queue
       
        q; 30 bool bfs(){ 31     rep(i,S,T){ 32         dep[i]=0; 33         oc[i]=fst[i]; 34     } 35     while(!q.empty()) q.pop(); 36  37     dep[bg]=1;q.push(bg); 38     while(!q.empty()){ 39         int fa=q.front();q.pop(); 40         for(int i=fst[fa];i;i=nxt[i]){ 41             int son=to[i]; 42             if(dep[son]==0&&f[i]>0){ 43                 dep[son]=dep[fa]+1; 44                 q.push(son); 45  46                 if(son==ed) return 1; 47             } 48         } 49     } 50  51     return 0; 52 } 53 ll dfs(int fa,ll fl){ 54     if(fa==ed||fl==0) return fl; 55  56     ll ans=0,F; 57     for(int &i=oc[fa];i;i=nxt[i]){ 58         int son=to[i]; 59         if(dep[son]==dep[fa]+1&&f[i]>0){ 60             F=dfs(son,min(fl,f[i])); 61  62             fl-=F;f[i]-=F; 63             ans+=F;f[i^1]+=F; 64  65             if(fl==0) break; 66         } 67     } 68  69     return ans; 70 } 71 ll fl(int B,int E,ll Inf){ 72     bg=B;ed=E; 73  74     ll ans=0,F; 75     while(bfs()) while(F=dfs(bg,Inf)) ans+=F; 76     return ans; 77 } 78  79  80 int main(){ 81     int cs; 82     scanf("%d",&cs); 83     while(cs--){ 84         scanf("%d",&n); 85         rep(i,1,n) scanf("%d",&a[i]); 86         rep(i,1,n) scanf("%d",&b[i]); 87         rep(i,1,n) scanf("%d",&c[i]); 88  89         //init 90         S=1;T=(n+1)<<1;len=1; 91         rep(i,S,T) fst[i]=0; 92         rep(i,1,n) add(i<<1,i<<1|1,b[i]); 93  94         int l[NN],mx=0; 95         rep(i,1,n){ 96             l[i]=1; 97             rep(j,1,i-1) 98                 if(a[j]
        
          pr;111         pr.clear();112         rep(i,1,n) pr.pb(mp(c[i],i));113         sort(pr.begin(),pr.end());114 115 116         printf("%lld ",fl(S,T,INF));117         vector
         
           ans;118         ans.clear();119 120         rep(i,0,n-1){121             int no=pr[i].second;122             bg=no<<1;ed=no<<1|1;123 124             if(bfs()) continue;125             126             ans.pb(no);127             fl(T,no<<1|1,b[no]);128             fl(no<<1,S,b[no]);129             f[no<<1]=f[no<<1|1]=0;130         }131 132         sort(ans.begin(), ans.end());133         printf("%d\n",(int)ans.size());134         rep(i,0,(int)ans.size()-1) 135             printf("%d ",ans[i]);136         printf("\n");137     }138 }