算法1

(二分) $O(m*logm * 玄学的dinic)$

C++ 代码

const int INF = 0x3f3f3f3f;
const int N = 1050,M = N * 100;
int mod = 1e9 +7;
int n,m,k,S,T;
int a[N][22],w[N];
int e[M],ne[M],f[M],h[N],idx;
void add(int a,int b,int c){
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
int d[N],cur[N];
bool bfs(){
    queue<int> q;
    q.push(S);
    memset(d,0,sizeof(d));
    d[S] = 1,cur[S] = h[S];
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = h[u] ; ~i ; i = ne[i]){
            int ver = e[i];
            if(!d[ver] && f[i]){
                d[ver] = d[u] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                q.push(ver); 
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u] ; ~i && flow < limit ; i = ne[i]){
        int ver = e[i];
        cur[u] = i;
        if(d[ver] == d[u] + 1 && f[i]){
            int k = find(ver,min(f[i],limit - flow));
            if(!k) d[ver] = 0;
            f[i] -= k,f[i ^ 1] += k,flow += k;
        }
    }
    return flow;
} 
int dinic(){
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r += flow;
    return r;
}
bool check(int len){
    for(int i = 1 ; i + len - 1 <= m ; ++i){
        int l = i,r = i + len - 1;
        memset(h,-1,sizeof(h));idx = 0;
        //从源点向每头牛牛连容量为1的边
        for(int j = 1 ; j <= n ; ++j) add(S,j,1);
        //从每个谷仓向汇点连容量为谷仓容积的边
        for(int j = 1 ; j <= m ; ++j) add(j + n,T,w[j]);
        //从所有牛牛向所有满意度在l~r的谷仓连容量为1的边
        for(int j = l ; j <= r ; ++j){
            for(int k = 1 ; k <= n ; ++k){
                add(k,n + a[k][j],1);
            }
        }
        if(dinic() == n) return true;
    }
    return false;
}
void solve(){
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= m ; ++j){
            cin >> a[i][j];
        }
    } 
    for(int i = 1 ; i <= m ; ++i) cin >> w[i];
    S = 0,T = n + m + 1;
    //二分区间长度
    int l = 1,r = m;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
}

signed main(){
    IOS;
    solve();
    return 0;
}

算法2

(双指针) $O(m*玄学的dinic)$

C++ 代码

const int N = 1050,M = N * 100;
int mod = 1e9 +7;
int n,m,k,S,T;
int a[N][22],w[N];
int e[M],ne[M],f[M],h[N],idx;
void add(int a,int b,int c){
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
int d[N],cur[N];
bool bfs(){
    queue<int> q;
    q.push(S);
    memset(d,0,sizeof(d));
    d[S] = 1,cur[S] = h[S];
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = h[u] ; ~i ; i = ne[i]){
            int ver = e[i];
            if(!d[ver] && f[i]){
                d[ver] = d[u] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                q.push(ver); 
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u] ; ~i && flow < limit ; i = ne[i]){
        int ver = e[i];
        cur[u] = i;
        if(d[ver] == d[u] + 1 && f[i]){
            int k = find(ver,min(f[i],limit - flow));
            if(!k) d[ver] = 0;
            f[i] -= k,f[i ^ 1] += k,flow += k;
        }
    }
    return flow;
} 
int dinic(){
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r += flow;
    return r;
}
bool check(int l,int r){
    memset(h,-1,sizeof(h));idx = 0;
    //从源点向每头牛牛连容量为1的边
    for(int j = 1 ; j <= n ; ++j) add(S,j,1);
    //从每个谷仓向汇点连容量为谷仓容积的边
    for(int j = 1 ; j <= m ; ++j) add(j + n,T,w[j]);
    //从所有牛牛向所有满意度在l~r的谷仓连容量为1的边
    for(int j = l ; j <= r ; ++j){
        for(int k = 1 ; k <= n ; ++k){
            add(k,n + a[k][j],1);
        }
    }
    if(dinic() == n) return true;
    return false;
}
void solve(){
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= m ; ++j){
            cin >> a[i][j];
        }
    } 
    for(int i = 1 ; i <= m ; ++i) cin >> w[i];
    S = 0,T = n + m + 1;
    int l,r;
    int ans = m;
    for(l = 0,r = 1; r <= m ; ++r ){
        while(l < r && check(l + 1,r)) l ++;
        if(check(l,r)) ans = min(ans,r - l + 1);
    }
    cout << ans << endl;
}

signed main(){
    IOS;
    solve();
    return 0;
}