ABC193 F. Zebraness

Difficulty:2475

問題

1辺にNタイルある正方形が与えられる。N*Nのタイルに色をつけて、隣接する色が異なる部分を最大化したい。いくつかのタイルはすでに塗る色が決まっている。隣接する色が異なる箇所は最大でいくつになるか？

解法

2N(N-1)を獲得したことにして、損を最小化する。i+jが奇数である点の白黒を反転することで最小カット問題に帰着する。

実装

code:cpp

bool solve(){

LL(n);

vector<str>s(n);

cin >> s;

mf_graph<ll>g(n*n+2);

ll S = n*n,T = n*n+1;

rep(i,n){

rep(j,n){

if(j+1<n){

g.add_edge(i*n+j,i*n+j+1,1);

g.add_edge(i*n+j+1,i*n+j,1);

}

if(i+1<n){

g.add_edge(i*n+j,i*n+j+n,1);

g.add_edge(i*n+j+n,i*n+j,1);

}

g.add_edge(S,i*n+j,INF);

}

else{

g.add_edge(i*n+j,T,INF);

}

}

}

O(2*n*(n-1) - g.flow(S,T));

return true;

}