P3308 [SDOI2014]LIS

· · 题解

一道网络流建模+贪心求割边边集好题。

从数据范围以及求最长上升子序列相关，不难想到这道题。

具体的，考虑用一个流量来表示一个最长上升子序列。

一个较为显然的结论是，求出 \text{dp}[i] 表示以 i 为结尾的最长上升子序列的长度后，i 这个位置在最长上升序列中只能位于第 \text{dp}[i] 个位置显然很显然，即我们的最长上升子序列的下标序列 \text{pos} 一定满足 \text{dp}[\text{pos}[i]]=i 。

那么如果我们将所有的点满足 i<j 且 \text{dp}[i]=\text{dp}[j]-1 的位置 (i,j) 建立一条由 i 指向 j 的边，令最长上升子序列的长度为了 \text{len}，那么任意一条最长上升子序列就可以表示为一条从 \text{dp}[s]=1 的点到 \text{dp}[t]=\text{len} 的点的一条路径，而回到这题的要求便是破坏所有的这种路径。

容易发现这题允许破坏的是”点“，那么最终的建图也基本明朗了起来。

1.将这 n 个点拆为两个点即入点和出点，并将每个入点向对应出点连一条流量为 B[i] 的边，表示破坏掉这个点的代价是 B[i]，也就是这题中，我们用”最小割“来表示“最小的破坏代价”。

2.将所有满足 \text{dp}[i]=1 的点，建立一条由源点 \text{S} 到 i 入点的，流量为 \text{inf} 的边；将所有满足 \text{dp}[j]=\text{len} 的点，建立一条由 j 出点到 汇点 \text{T} 的，流量为 \text{inf} 的边。

3.将所有的点满足 i<j 且 \text{dp}[i]=\text{dp}[j]-1 的位置 (i,j) 建立一条由 i 出点指向 j 入点的，流量为 \text{inf} 的边。这样一条条形如 \text{S} -> \text{pos}[1]入点 -> \text{pos}[1]出点 -> \text{pos}[2]入点 -> \text{pos}[2]出点 -> \dots -> \text{pos}[\text{len}]入点 -> \text{pos}[\text{len}]出点 -> \text{T} 的增广路即为一条条最长上升子序列。而流量为 \text{inf} 则表示不可破坏，实际上也就是我们只允许破坏每条"入点连向对应出点的边“。

最后跑一遍 \text{S} 到 \text{T} 的最小割即可求出第一问的最小代价。

再考虑如何确定出附加属性字典序最小的最小割割边边集。

首先容易发现的是，成为割边的一定是”入点连向对应出点的边“，这显然是我们一手策划的，将题目中的 C 数组 \text{sort} 之后，按顺序考虑每条边是否可能成为割边，如果可能的话就强制钦定它为割边。

具体实现的时候也不需要其他题解那么麻烦，判断一条边是否为割边，显然就是从该边的入点无法到达出点（当然不走流量为 0 的边），代码实现上只需要调用一遍 \text{dinic} 中的 \text{bfs} 函数即可。而强制钦定他为割边只需要将所有边复原后，删除这条边（将它和它的反向边流量都置为 0 即可），再重新跑一遍 S 到 T 的最小割用以得到新图的最小割即可。

最后将得到的”需破坏点“下标 \text{sort} 一遍即可。

复杂度就是 n 遍 \text{dinic} 的复杂度，如果将边的数量看作 n^2 的话，复杂度就是 \Theta(n^5) 实际上哪里都不满

最后放一下代码

inline void add(rint x,rint y,rint flow)
{
    e[++cnt]=(Edge){y,head[x],flow},head[x]=cnt;
}

int bfs(rint s,rint t)
{
    memset(dis,0,sizeof(dis)),memcpy(tmphead,head,sizeof(head));
    queue<int> q;q.push(s),dis[s]=1;
    while(!q.empty())
    {
        rint u=q.front();q.pop();
        for(rint i=head[u];i;i=e[i].next)
        {
            rint v=e[i].to;
            if(!e[i].flow||dis[v]) continue;
            dis[v]=dis[u]+1,q.push(v);
            if(v==t) return 1;
        }
    }
    return 0;
}

int dfs(rint x,rint t,rint flow)
{
    if(x==t) return flow;
    rint rest=flow;
    for(rint i=tmphead[x];i;i=e[i].next)
    {
        tmphead[x]=i;rint v=e[i].to;
        if(!e[i].flow||dis[v]!=dis[x]+1) continue;
        rint tmp=dfs(v,t,min(rest,e[i].flow));
        tmp?e[i].flow-=tmp,e[i^1].flow+=tmp,rest-=tmp:dis[v]=0;
        if(!rest) return flow;
    }
    return flow-rest;
}

inline void add_edge(rint x,rint y,rint flow)
{
    add(x,y,flow),add(y,x,0);
}

int main()
{
    for(rint tt=read<int>();tt;tt--)
    {
        rint n=read<int>(),mx=0,s=0,t=n*2+1;memset(head,0,t+1<<2),cnt=1;
        for(rint i=1;i<=n;i++) a[i]=read<int>();
        for(rint i=1;i<=n;i++)
        {
            dp[i]=1;
            for(rint j=1;j<i;j++)
                if(a[i]>a[j])
                    dp[i]=max(dp[i],dp[j]+1);
            mx=max(mx,dp[i]);
        }
        for(rint i=1;i<=n;i++) add_edge(i,i+n,read<int>());
        for(rint i=1;i<=n;i++)
        {
            if(dp[i]==1) add_edge(s,i,inf);
            if(dp[i]==mx) add_edge(i+n,t,inf);
            for(rint j=i+1;j<=n;j++)
                if(a[i]<a[j]&&dp[j]==dp[i]+1)
                    add_edge(i+n,j,inf);
        }
        for(rint i=1;i<=n;i++) c[i]=(Node){read<int>(),i};
        sort(c+1,c+n+1,[](const Node &x,const Node &y){return x.val<y.val;});
        rll ans=0;rint N=0;
        while(bfs(s,t)) ans+=dfs(s,t,inf);
        for(rint i=1;i<=n;i++)
        {
            rint u=c[i].id,v=u+n;
            if(!bfs(u,v))
            {
                b[++N]=u,e[u*2].flow=e[u*2+1].flow=0;
                for(rint i=2;i<=cnt;i+=2) e[i].flow+=e[i^1].flow,e[i^1].flow=0;
                while(bfs(s,t)) dfs(s,t,inf);
            }
        }
        sort(b+1,b+N+1),printf("%lld %d\n",ans,N);
        for(rint i=1;i<=N;i++) printf("%d ",b[i]);puts("");
    }
    return 0;
}