Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment