正题

题目链接: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【最小割】

正题

题目大意

解题思路

code

最新文章

热门文章