Created
October 26, 2016 14:36
-
-
Save Yazaten/40b4ad34df409b059015e61f83c85ee3 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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