正題

題目鏈接:https://www.luogu.com.cn/problem/P3308

---

題目大意

三個$n$個數字的序列$A,B,C$。要求刪除其中某些位置$i$使得$A$的最長上升子序列至少減少$1$且刪去位置$B$的權值和最小的情況下滿足刪去位置的$C$值升序排序后字典序最小。

---

解題思路

首先$B$值最小很好求，跑一遍$LIS$的$dp$，然后每個點拆成兩個點，然后如果$f[x]$轉移到$f[y]$是最優的就建邊然后跑最小割就好了。
大體和P2766 最長不下降子序列問題差不多

也就是現在我們要求字典序最小的最小割，需要利用到最小割的性質。

如果一條邊$x,y$是可行割，那么它滿足在殘量網絡上$x$到達不了$y$。

首先如果$x?>y$沒有滿流那么肯定不是最小割，其次如果滿流了但是還有一條$x$到$y$的路徑，那么證明如果走這條增廣路一定可以使最大流更大，所以也不是最小割。

那么這樣我們就可以判斷一條邊是否可行了，然后需要消去其他等價邊的影響，大體方法是從$T$到$y$跑一次$dinic$，再從$x$到$S$跑一次$dinic$。這個操作叫退流，這樣殘量網絡就變成了滿流邊$x?>y$的殘量網絡了。

先跑一次$dinic$，然后按照$C$值排序，從小到大判斷加入邊即可。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #define ll long long using namespace std; const ll N=710*2,inf=1e18; struct node{ll to,next,w; }a[N*N]; ll T,n,tot,ls[N],dep[N],A[N],B[N],C[N],f[N],p[N]; vector<ll> prt;queue<ll> q; void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0; } bool bfs(ll s,ll t){while(!q.empty())q.pop();q.push(s);memset(dep,0,sizeof(dep));dep[s]=1;while(!q.empty()){ll x=q.front();q.pop();for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(dep[y]||!a[i].w)continue;dep[y]=dep[x]+1;if(y==t)return 1;q.push(y);}}return 0; } ll dinic(ll x,ll t,ll flow){if(x==t)return flow;ll rest=0,k;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(dep[x]+1!=dep[y]||!a[i].w)continue;rest+=(k=dinic(y,t,min(flow-rest,a[i].w)));a[i].w-=k;a[i^1].w+=k;if(rest==flow)return flow;}if(!rest)dep[x]=0;return rest; } bool cmp(ll x,ll y) {return C[x]<C[y];} signed main() {scanf("%lld",&T);while(T--){memset(ls,0,sizeof(ls));tot=1;scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&A[i]);for(ll i=1;i<=n;i++)scanf("%lld",&B[i]);for(ll i=1;i<=n;i++)scanf("%lld",&C[i]);ll maxs=0,s=2*n+1,t=s+1;for(ll i=1;i<=n;i++){f[i]=1;p[i]=i;for(ll j=1;j<i;j++)if(A[i]>A[j])f[i]=max(f[i],f[j]+1);maxs=max(maxs,f[i]);}for(ll i=1;i<=n;i++){if(f[i]==1)addl(s,i,inf);if(f[i]==maxs)addl(i+n,t,inf);addl(i,i+n,B[i]);for(ll j=i+1;j<=n;j++)if(A[i]<A[j]&&f[i]+1==f[j])addl(i+n,j,inf);}ll ans=0;prt.clear();while(bfs(s,t))ans+=dinic(s,t,inf);printf("%lld ",ans);sort(p+1,p+1+n,cmp);for(ll i=1;i<=n;i++){ll x=p[i];if(bfs(x,x+n))continue;while(bfs(t,x+n))dinic(t,x+n,inf);while(bfs(x,s))dinic(x,s,inf);prt.push_back(x);}printf("%lld\n",prt.size());sort(prt.begin(),prt.end());for(ll i=0;i<prt.size();i++)printf("%lld ",prt[i]);putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的P3308-[SDOI2014]LIS【最小割】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。