[ARC176E] Max Vector 题解

题目链接

点击打开链接

题目解法

这个题的一个转化很关键：
把一次操作 \(j\) 等价看作 必须满足 \((\forall_{1\le i\le n}X_i\ge a_{j,i})|(\forall_{1\le i\le n}Y_i\ge a_{j,i})=1\)
正确性是显然的

另外的一个关键思路是网络流
有了上面的转化，我们考虑切糕模型（其实接下来都好想了）
对于 \(X\) 序列，我们从 \(1\) 到 \(V\) 连链
对于 \(Y\) 序列，我们从 \(V\) 到 \(1\) 连链
最初序列的限制是好满足的
考虑一次操作如何连边：我们建虚点，然后 \(Y\) 序列的表示 \(<a_{j,i}\) 的向虚点连边，虚点向 \(X\) 序列的表示 \(<a_{j,i}\) 的虚点连边

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int inf=1e9;
namespace Dinic{
    const int NN=12000,MM=100000;
    int S,T;
    int e[MM],f[MM],ne[MM],h[NN],idx;
    int d[NN],cur[NN];
    queue<int> Q;
    void clr(){ ms(h,-1);idx=0;}
    void add(int x,int y,int z){ e[idx]=y,f[idx]=z,ne[idx]=h[x],h[x]=idx++;}
    void add_edge(int x,int y,int z){ add(x,y,z),add(y,x,0);}
    bool bfs(){
        while(!Q.empty()) Q.pop();
        ms(d,-1);
        d[S]=0,cur[S]=h[S],Q.push(S);
        while(!Q.empty()){
            int u=Q.front();Q.pop();
            if(u==T) return 1;
            for(int i=h[u];~i;i=ne[i]){
                int v=e[i];
                if(f[i]&&d[v]==-1) d[v]=d[u]+1,cur[v]=h[v],Q.push(v);
            }
        }
        return 0;
    }
    int find(int u,int lmt){
        if(u==T) return lmt;
        int res=0;
        for(int i=cur[u];~i&&res<lmt;i=ne[i]){
            cur[u]=i;
            int v=e[i];
            if(d[u]+1==d[v]&&f[i]){
                int t=find(v,min(f[i],lmt-res));
                if(!t) d[v]=-1;
                res+=t,f[i]-=t,f[i^1]+=t;
            }
        }
        return res;
    }
    int dinic(){
        int res=0,add;
        while(bfs()) while(add=find(S,inf)) res+=add;
        return res;
    }
}
const int N=15,M=510;
int n,m,x[N],y[N],a[M][N];
int ind(int x,int y){ return (x-1)*501+y;}
int main(){
    read(n),read(m);
    F(i,1,n) read(x[i]);
    F(i,1,n) read(y[i]);
    F(i,1,m) F(j,1,n) read(a[i][j]);
    Dinic::S=n*2*501+m+5,Dinic::T=Dinic::S+1;
    Dinic::clr();
    F(i,1,n){
        Dinic::add_edge(Dinic::S,ind(i,1),inf);
        F(j,1,500) Dinic::add_edge(ind(i,j),ind(i,j+1),j);
        F(j,1,500) Dinic::add_edge(ind(i,j+1),ind(i,j),inf);
        Dinic::add_edge(ind(i,501),Dinic::T,inf);
    }
    F(i,n+1,2*n){
        Dinic::add_edge(Dinic::S,ind(i,501),inf);
        F(j,1,500) Dinic::add_edge(ind(i,j+1),ind(i,j),j);
        F(j,1,500) Dinic::add_edge(ind(i,j),ind(i,j+1),inf);
        Dinic::add_edge(ind(i,1),Dinic::T,inf);
    }
    F(i,1,n) Dinic::add_edge(Dinic::S,ind(i,x[i]),inf);
    F(i,1,n) Dinic::add_edge(ind(i+n,y[i]),Dinic::T,inf);
    F(i,1,m){
        int nw=n*2*501+i;
        F(j,1,n){
            Dinic::add_edge(ind(j+n,a[i][j]),nw,inf);
            Dinic::add_edge(nw,ind(j,a[i][j]),inf);
        }
    }
    printf("%d\n",Dinic::dinic());
    return 0;
}