ARC056C.cpp

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define pii pair<int,int>
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)

#define MAX_V 17


/******************** dinic ********************/
struct edge{int to,cap,rev;};

vector<edge> G[MAX_V];  //グラフのパス
int level[MAX_V];       //始点からの距離
int iter[MAX_V];        //どこまで調べたか

// fromからtoへ向かう、容量capの辺をグラフに追加する
void add_edge(int from,int to,int cap){
    G[from].push_back(  (edge){ to  ,cap,(int)G[to  ].size()   }  );
    G[to  ].push_back(  (edge){ from,0  ,(int)G[from].size()-1 }  );
}

// sからの最短距離をBFSで計算する
void bfs(int s){
    rep(i,MAX_V)level[i]=-1;
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v=que.front();que.pop();
        
        rep(i,G[v].size()){
            edge &e=G[v][i];
            if(e.cap>0 && level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}

//増加パスをDFSで探す
int dfs(int v,int t,int f){
    if(v==t)return f;
    for(int &i=iter[v];i<G[v].size();i++){
        edge &e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

// sからtへの最大流を求める
int max_flow(int s,int t){
    if(s==t)return INF;
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>0){
            flow+=f;
        }
    }
}
/******************** dinic ********************/



int d[MAX_V][MAX_V];

void dfs(int pos,vector<bool> &used,map<int,bool> mp){  //残余グラフ上で、ソースからたどり着ける頂点を調べる
    for(auto &e:G[pos]){
        if(mp.count(e.to)!=0&&e.cap>0&&!used[e.to]){
            used[e.to]=true;
            dfs(e.to,used,mp);
        }
    }
}


int n,k;

ll solve(vector<int> v){
    if(v.size()==1)return k;

    rep(i,MAX_V)G[i].clear();   //「引数の頂点集合」以外を取り除いたグラフを構成する
    rep(i,v.size()){
        rep(j,v.size()){
            if(d[v[i]][v[j]]!=0)add_edge(v[i],v[j],d[v[i]][v[j]]);
        }
    }
    
    vector<edge> Gp[MAX_V];     //グラフのコピー
    rep(i,MAX_V)Gp[i] = G[i];
    
    int minimum_minCut = INF;   //最小の、最小カットの値
    int mmc_s,mmc_t;
    rep(i,v.size()){            //ソースとシンクを変えながらフローを流して最小カットの値を調べる
        rep(j,v.size()){
            if(v[i]==v[j])continue;
            int res = max_flow(v[i],v[j]);
            if(res<minimum_minCut){
                minimum_minCut = res;
                tie(mmc_s,mmc_t) = tie(v[i],v[j]);
            }
            rep(k,MAX_V)G[k] = Gp[k];   //G[] は残余グラフと化しているため、元のグラフに戻す
        }
    }
    if(minimum_minCut>k)return k;
    
    
    max_flow(mmc_s,mmc_t);
    
    map<int,bool> mp;
    rep(i,v.size())mp[v[i]]=true;
    
    vector<bool> used(v.size(),false);
    used[mmc_s]=true;
    dfs(mmc_s,used,mp);
    
    vector<int> usedV,un_usedV;
    rep(i,n){
        if(used[i])usedV.pb(i);
        else if(mp.count(i)!=0)un_usedV.pb(i);
    }
    return solve(usedV) + solve(un_usedV) - minimum_minCut; //カットしてできた2つの部門のスコアの和 - 最小カット
}


int main(){
    rep(i,MAX_V)rep(j,MAX_V)d[i][j] = INF;
    cin>>n>>k;
    rep(i,n){
        rep(j,n){
            cin>>d[i][j];
        }
    }
    
    vector<int> v;
    rep(i,n)v.pb(i);

    cout<<solve(v)<<endl;
}