verify/kattis/thekingofthenorth.cpp

• View this file on GitHub
• Last update: 2024-10-31 23:18:18+07:00

Depends on

• flow/dinic.hpp
• template.hpp

Code

#include "template.hpp"
#include "flow/dinic.hpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector a(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> a[i][j];
        }
    }
    int x,y;
    cin >> x >> y;
    Dinic<ll> mf(n*m*2+1,(x*m+y)*2,n*m*2);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int u=i*m+j;
            mf.add_edge(u*2,u*2+1,a[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<m;j++){
            int u=i*m+j-1,v=i*m+j;
            mf.add_edge(u*2+1,v*2,LINF);
            mf.add_edge(v*2+1,u*2,LINF);
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            int u=(i-1)*m+j,v=i*m+j;
            mf.add_edge(u*2+1,v*2,LINF);
            mf.add_edge(v*2+1,u*2,LINF);
        }
    }
    for(int i=0;i<n;i++){
        mf.add_edge(i*m*2+1,mf.t,LINF);
        mf.add_edge((i*m+m-1)*2+1,mf.t,LINF);
    }
    for(int i=1;i<m-1;i++){
        mf.add_edge(i*2+1,mf.t,LINF);
        mf.add_edge(((n-1)*m+i)*2+1,mf.t,LINF);
    }
    cout << mf.flow();
}

#line 1 "template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=INT_MAX/2;
const int MOD=998244353;
const int MOD2=1000000007;
const ll LINF=LLONG_MAX/2;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));

template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "flow/dinic.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-07-15
 * Description: Dinic's Algorithm for finding the maximum flow.
 * Time: O(V E \log U) where U is the maximum flow.
 */

template<class T,bool directed=true,bool scaling=true>
struct Dinic{
    static constexpr T INF=numeric_limits<T>::max()/2;
    struct Edge{
        int to;
        T flow,cap;
        Edge(int _to,T _cap):to(_to),flow(0),cap(_cap){}
        T remain(){return cap-flow;}
    };
    int n,s,t;
    T U;
    vector<Edge> e;
    vector<vector<int>> g;
    vector<int> ptr,lv;
    bool calculated;
    T max_flow;
    Dinic(){}
    Dinic(int n,int s,int t){init(n,s,t);}
    void init(int _n,int _s,int _t){
        n=_n,s=_s,t=_t;
        U=0;
        e.clear();
        g.assign(n,{});
        calculated=false;
    }
    void add_edge(int from,int to,T cap){
        assert(0<=from&&from<n&&0<=to&&to<n);
        g[from].emplace_back(e.size());
        e.emplace_back(to,cap);
        g[to].emplace_back(e.size());
        e.emplace_back(from,directed?0:cap);
        U=max(U,cap);
    }
    bool bfs(T scale){
        lv.assign(n,-1);
        vector<int> q{s};
        lv[s]=0;
        for(int i=0;i<(int)q.size();i++){
            int u=q[i];
            for(int j:g[u]){
                int v=e[j].to;
                if(lv[v]==-1&&e[j].remain()>=scale){
                    q.emplace_back(v);
                    lv[v]=lv[u]+1;
                }
            }
        }
        return lv[t]!=-1;
    }
    T dfs(int u,int t,T f){
        if(u==t||f==0)return f;
        for(int &i=ptr[u];i<(int)g[u].size();i++){
            int j=g[u][i];
            int v=e[j].to;
            if(lv[v]==lv[u]+1){
                T res=dfs(v,t,min(f,e[j].remain()));
                if(res>0){
                    e[j].flow+=res;
                    e[j^1].flow-=res;
                    return res;
                }
            }
        }
        return 0;
    }
    T flow(){
        if(calculated)return max_flow;
        calculated=true;
        max_flow=0;
        for(T scale=scaling?1LL<<(63-__builtin_clzll(U)):1LL;scale>0;scale>>=1){
            while(bfs(scale)){
                ptr.assign(n,0);
                while(true){
                    T f=dfs(s,t,INF);
                    if(f==0)break;
                    max_flow+=f;
                }
            }
        }
        return max_flow;
    }
    pair<T,vector<int>> cut(){
        flow();
        vector<int> res(n);
        for(int i=0;i<n;i++)res[i]=(lv[i]==-1);
        return {max_flow,res};
    }
};

#line 3 "verify/kattis/thekingofthenorth.cpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    vector a(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> a[i][j];
        }
    }
    int x,y;
    cin >> x >> y;
    Dinic<ll> mf(n*m*2+1,(x*m+y)*2,n*m*2);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int u=i*m+j;
            mf.add_edge(u*2,u*2+1,a[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<m;j++){
            int u=i*m+j-1,v=i*m+j;
            mf.add_edge(u*2+1,v*2,LINF);
            mf.add_edge(v*2+1,u*2,LINF);
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<m;j++){
            int u=(i-1)*m+j,v=i*m+j;
            mf.add_edge(u*2+1,v*2,LINF);
            mf.add_edge(v*2+1,u*2,LINF);
        }
    }
    for(int i=0;i<n;i++){
        mf.add_edge(i*m*2+1,mf.t,LINF);
        mf.add_edge((i*m+m-1)*2+1,mf.t,LINF);
    }
    for(int i=1;i<m-1;i++){
        mf.add_edge(i*2+1,mf.t,LINF);
        mf.add_edge(((n-1)*m+i)*2+1,mf.t,LINF);
    }
    cout << mf.flow();
}

Back to top page