燃やす埋める問題についてまとめ
燃やす埋める系の問題をまとめて解いたので、学んだ点について書き残しておく。
燃やす埋める問題とは以下の様な問題である。
いくつかのものが与えられて、それを赤か青に塗り分ける必要がある（燃やすか埋めるか）。それぞれがどちらの色に属するかによって得られるスコアが異なる。
最適に色を塗り分けた時の、スコアを最大値を求めよ。
更に条件として、あるものが赤に属して別のあるものが青に属する場合は罰金、もしくは、あるものが赤に属して別のあるものも赤に属する場合は利得が得られるという依存関係がいくつも与えられる。
この様な問題は解き方が定型化されており、最大流問題に帰着し、適切なグラフを構築してその最小カットを求めることで解くことが可能である。
- いくつかの注意点
- 例題
- ARC 085 E - MUL
- ABC 010 D - 浮気予防
- TopCoder SRM 594 Div I FoxAndGo3
- RUPC 2019 Day 2 H - Ghost
- Educational Codeforces Round 55 G. Petya and Graph
- RUCPC 2019 Day 1 G イルミネーション
- Google Code Jam 2008 World Finals - The Year of Code Jam
- 参考
いくつかの注意点
1. 扱えない条件がある
あるものが赤で別のあるものも赤であるなら罰金、または、あるものが赤で別のあるものが青であるなら利得という依存関係は最小カットで求めることは困難である。一見似た条件に見えるが、これらは最大カットを求める問題になる。（参考）
2. 構築するグラフに負辺は含まれてはいけない
燃やす埋める系問題では、利得や罰金の値が負で与えられる場合がある。負辺があるグラフの最小カット問題はNP困難問題となる（参考に載せた診断人さんのスライドP.22を参照）。そのため条件に負の値が与えられたときは、適宜言い換えを行う必要がある。燃やす埋める系の問題ではよくこの言い換え求められる場面が多く、以下に載せた例題の解法にも使われている。
例題
ARC 085 E - MUL
問題
N個の宝石が与えられてそれぞれの価値が である。そのぞれの宝石について、残すか割るかを選ぶことができ、残した場合は
を、割った場合は0円の得る。さらに、
を割ったならば、
の倍数の宝石も必ず割る必要がある。得られる金額の最大値を求めよ。
制約
解説
この手の利得が負数の場合があり、それを辺のキャパシティとしてそのまま使えないという場合は、一旦全ての利得が得られるものと仮定して、その内の得られないもの最小カットで求めて、罰金として仮定した利得から減算する、という解き方がフレームワークとして使える。
この問題の場合 であるものを利得として全て得られると仮定する。
最小カットを求めるグラフは、必ず残すに属する頂点 S と、必ず割るに属する頂点 T と、N個の宝石の S - (n頂点) - Tというグラフを作り、宝石iを残すなら 、割るなら
の罰金があるとして辺を張る。
宝石iを割るならiの倍数の宝石も必ず割る、という条件は言い換えると、宝石iが割るに属して、iの倍数の宝石のどれかが残すに属する、ということは許されないということになる。
「許されない」という依存関係を表したい場合は、そのようにグラフをカットした場合、それが必ず最小カットにはならないようにすればよく、この場合は頂点iからiの倍数の頂点に無限に相当するcapacityの辺を張ることで表現できる。
上記のグラフのS-T間の最小カットが仮定した利得にたいする罰金の最小値となるので、答えは（仮定した利得）-（グラフの最小カット）となる。
解答コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
using ll = long long;
template<class t> using vc=vector<t>;
const ll INF = 1e9+10;
template <class T>
class Dinic {
private:
const int INF = 1e9;
vector<int> level, itr;
struct Edge {
int to, rev; T cap;
Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
};
vector<vector<Edge>> G;
Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
void bfs(int s) {
level.assign(G.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto &e : G[v]) {
if (level[e.to] < 0 and e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T flow) {
if (v == t) return flow;
for (int &i = itr[v]; i < G[v].size(); i++) {
auto &edge = G[v][i];
if (level[v] < level[edge.to] and edge.cap > 0) {
auto f = dfs(edge.to, t, min(flow, edge.cap));
if (f > 0) {
edge.cap -= f;
get_rev(edge).cap += f;
return f;
}
}
}
return 0;
}
public:
Dinic(int n) { G.resize(n); }
void add_edge(int from, int to, T cap) {
G[from].push_back(Edge(to, (int)G[to].size(), cap));
G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
}
T get_max_flow(int s, int t) {
int n = G.size();
T res = 0;
while (true) {
itr.assign(n, 0);
bfs(s);
if (level[t] < 0) break;
while (true) {
T flow = dfs(s, t, INF);
if (flow > 0) res += flow;
else break;
}
}
return res;
}
};
signed main()
{
cin.tie( 0 ); ios::sync_with_stdio( false );
int n; cin>>n;
vc<ll> a(n);
ll ans=0;
rep(i,n) {
cin>>a[i];
ans+=max(a[i], 0LL);
}
auto flow=Dinic<ll>(n+2);
int s=n, t=n+1;
rep(i,n){
flow.add_edge(s,i,max(-a[i],0LL));
flow.add_edge(i,t,max(a[i],0LL));
for(int j=i+(i+1); j<n; j+=(i+1)){
flow.add_edge(i,j,INF);
}
}
ans-=flow.get_max_flow(s,t);
cout<<ans<<endl;
}
ABC 010 D - 浮気予防
これは参考に載せたyosupoさんの記事にも挙げられている問題。
問題
N頂点E辺のグラフがあって、頂点0からアクセスできないようにしたい頂点がG個ある。G個の頂点にアクセスできないようにするためにできる操作が、①任意の辺を1つ取り除く、②任意の頂点を1つ無効化する（接続される辺は維持される）の2つあり、いずれもコスト1かかる。G個全てアクセスできないようにするためのコストの最小値を求めよ。
制約
解説
必ず頂点0側に属する頂点をS(=頂点0)、必ず頂点0側に属さない頂点をT(=頂点N)とする。頂点を無効化する、ということはその頂点から頂点Tへcapacity=1の辺を張ることで表現できるので、元のグラフに加えて、G個のアクセスできないようにしたい頂点と頂点Tに辺を張れば、S-T間の最小カットが求める解になる。
解答コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
using ll = long long;
template<class t> using vc=vector<t>;
const ll INF = 1e9+10;
template <class T>
class Dinic {
private:
const int INF = 1e9;
vector<int> level, itr;
struct Edge {
int to, rev; T cap;
Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
};
vector<vector<Edge>> G;
Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
void bfs(int s) {
level.assign(G.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto &e : G[v]) {
if (level[e.to] < 0 and e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T flow) {
if (v == t) return flow;
for (int &i = itr[v]; i < G[v].size(); i++) {
auto &edge = G[v][i];
if (level[v] < level[edge.to] and edge.cap > 0) {
auto f = dfs(edge.to, t, min(flow, edge.cap));
if (f > 0) {
edge.cap -= f;
get_rev(edge).cap += f;
return f;
}
}
}
return 0;
}
public:
Dinic(int n) { G.resize(n); }
void add_edge(int from, int to, T cap) {
G[from].push_back(Edge(to, (int)G[to].size(), cap));
G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
}
T get_max_flow(int s, int t) {
int n = G.size();
T res = 0;
while (true) {
itr.assign(n, 0);
bfs(s);
if (level[t] < 0) break;
while (true) {
T flow = dfs(s, t, INF);
if (flow > 0) res += flow;
else break;
}
}
return res;
}
};
signed main()
{
cin.tie( 0 ); ios::sync_with_stdio( false );
int n,g,e;
cin>>n>>g>>e;
int s=0, t=n;
auto flow=Dinic<int>(n+1);
rep(i,g){
int p; cin>>p;
flow.add_edge(p,t,1);
}
rep(i,e){
int a,b; cin>>a>>b;
flow.add_edge(a,b,1);
flow.add_edge(b,a,1);
}
cout<<flow.get_max_flow(s,t)<<endl;
}
TopCoder SRM 594 Div I FoxAndGo3
https://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706
診断人さんのスライドにも載っている問題。（P.36参照）
問題
N*Nの囲碁の盤面の情報が与えられる（各マスは空白、白、黒のいずれか）。任意の空白マスに好きなだけ黒石を置くことができ、黒で白を囲ったときその白石を取ることができる。黒石を最適に配置した時、最終的な空白マスの最大個数を求めよ。
制約
白石は左右上下に連続して配置されることはない
解説
空白と白は最終的に全て空白にできると仮定し、その仮定した個数から空白にできない個数の最小値を引くことで解を求める方針で解く。
空白、白が置かれているマスそれぞれについて、そのままにするか、変更するか（白を取る、空白に黒を置く）かの2つの操作が行えると考える。
必ずそのままにする頂点をS、必ず変更する頂点をTとし、N*N+2頂点のグラフに適切に辺を張ることで、最小カットが求めたい空白にできない個数の最小値になる。
以下はその辺の張り方。
- 空白マスは、そのままにするならコスト0、変更する（黒石を置く）ならコスト1掛かる、と捉えられる
- 白マスは、そのままにするならコスト1、変更する（白石を取る）ならコスト0掛かる、と捉えられる
更に白マスを変更するための条件を整理すると、ある白マスを変更するなら、その周囲の4マスにある空白は全て変更する必要がある、ということになる。 これは言い換えると、ある白マスを変更して、その周辺の空白マスのいずれかが変更されていない、ということは許されないということになる。 許されないという状態はcapacity=無限の辺を張れば表現できるので、白マスの頂点から周辺の空白マスへの頂点へその辺を張る。
解答コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
using ll = long long;
template<class t> using vc=vector<t>;
const ll INF = 1e9+10;
template <class T>
class Dinic {
private:
const int INF = 1e9;
vector<int> level, itr;
struct Edge {
int to, rev; T cap;
Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
};
vector<vector<Edge>> G;
Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
void bfs(int s) {
level.assign(G.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto &e : G[v]) {
if (level[e.to] < 0 and e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T flow) {
if (v == t) return flow;
for (int &i = itr[v]; i < G[v].size(); i++) {
auto &edge = G[v][i];
if (level[v] < level[edge.to] and edge.cap > 0) {
auto f = dfs(edge.to, t, min(flow, edge.cap));
if (f > 0) {
edge.cap -= f;
get_rev(edge).cap += f;
return f;
}
}
}
return 0;
}
public:
Dinic(int n) { G.resize(n); }
void add_edge(int from, int to, T cap) {
G[from].push_back(Edge(to, (int)G[to].size(), cap));
G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
}
T get_max_flow(int s, int t) {
int n = G.size();
T res = 0;
while (true) {
itr.assign(n, 0);
bfs(s);
if (level[t] < 0) break;
while (true) {
T flow = dfs(s, t, INF);
if (flow > 0) res += flow;
else break;
}
}
return res;
}
};
const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};
inline bool inside(int y, int x, int H, int W) {
return (y >= 0 && x >= 0 && y < H && x < W);
}
class FoxAndGo3{
public:
int h,w;
int node(int i, int j){
return i*w+j;
}
int maxEmptyCells(vector<string> mat){
h=mat.size(), w=mat[0].size();
int s=h*w, t=h*w+1;
auto flow=Dinic<int>(h*w+2);
int ans=0;
rep(i,h){
rep(j,w){
if(mat[i][j]=='x') continue;
ans++;
int now=node(i,j);
if(mat[i][j]=='.'){
flow.add_edge(s,now,0);
flow.add_edge(now,t,1);
}else{
flow.add_edge(s,now,1);
flow.add_edge(now,t,0);
rep(k,4){
int ni=i+dy[k], nj=j+dx[k];
if(inside(ni,nj,h,w) and mat[ni][nj]=='.'){
flow.add_edge(now,node(ni,nj),INF);
}
}
}
}
}
return ans-flow.get_max_flow(s,t);
}
};
// test
// signed main()
// {
// cin.tie( 0 ); ios::sync_with_stdio( false );
// auto f=FoxAndGo3();
// vc<string> mat(3);
// mat[0]="xox";
// mat[1]="o.o";
// mat[2]="xox";
// cout<<f.maxEmptyCells(mat)<<endl; // 4
// }
RUPC 2019 Day 2 H - Ghost
問題
N人の人がいて、最初それぞれ左右どちらかを向いている。各iについて初期状態と反対の方向を向くときコストA_iがかかる。更にM個の条件が与えられて、(x,y)が向き合っているならコストB_jがかかる。各人について最適に方向を決めた時のコストの最小値を求めよ。
制約
解説
最終的に必ず左を向いている頂点をS、必ず右を向いている頂点をTとして、N+2頂点のグラフに適切に辺を張ることで、S-T間の最小カットが求める解になる。
辺の張り方は以下の様になる。
まず各人iとS,T間にそれぞれ、初期方向と同じ方向ならコスト0、反対方向ならコストA_iの辺を張る。
また(x,y)が向き合っているということは、x<y であるとして、人xが右を向いていて人yが左を向いている状態である。よって、x→yへコストB_jのcapacityの辺を張ればよい。
解答コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
template<class t> using vc=vector<t>;
template <class T>
class Dinic {
private:
const int INF = 1e9;
vector<int> level, itr;
struct Edge {
int to, rev; T cap;
Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
};
vector<vector<Edge>> G;
Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
void bfs(int s) {
level.assign(G.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto &e : G[v]) {
if (level[e.to] < 0 and e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T flow) {
if (v == t) return flow;
for (int &i = itr[v]; i < G[v].size(); i++) {
auto &edge = G[v][i];
if (level[v] < level[edge.to] and edge.cap > 0) {
auto f = dfs(edge.to, t, min(flow, edge.cap));
if (f > 0) {
edge.cap -= f;
get_rev(edge).cap += f;
return f;
}
}
}
return 0;
}
public:
Dinic(int n) { G.resize(n); }
void add_edge(int from, int to, T cap) {
G[from].push_back(Edge(to, (int)G[to].size(), cap));
G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
}
T get_max_flow(int s, int t) {
int n = G.size();
T res = 0;
while (true) {
itr.assign(n, 0);
bfs(s);
if (level[t] < 0) break;
while (true) {
T flow = dfs(s, t, INF);
if (flow > 0) res += flow;
else break;
}
}
return res;
}
};
signed main()
{
cin.tie( 0 ); ios::sync_with_stdio( false );
int n,m; cin>>n>>m;
string u; cin>>u;
auto flow=Dinic<int>(n+2);
int s=n, t=n+1;
rep(i,n) {
int a; cin>>a;
if(u[i]=='L'){
flow.add_edge(s,i,0);
flow.add_edge(i,t,a);
}else{
flow.add_edge(s,i,a);
flow.add_edge(i,t,0);
}
}
rep(i,m){
int x,y,b; cin>>x>>y>>b; x--,y--;
if(x>y) swap(x,y);
flow.add_edge(x,y,b);
}
cout<<flow.get_max_flow(s,t)<<endl;
}
Educational Codeforces Round 55 G. Petya and Graph
問題
N頂点M辺のグラフが与えられる。各頂点、辺にはそれぞれ重みA、Wがあり、部分グラフの重みを（辺の重みの和）-（頂点の重みの和）とするとき、重みの最大値を求めよ。なお、部分グラフは連結である必要はない。
制約
解説
全ての辺の重みのみを得られると仮定し、仮定した合計から、（得られない辺の重み+含まなければならない頂点の重み）を引くことで解を求める。
各頂点、および各辺を部分グラフに含むか、含まないかのいずれかに分けたときの最小カットが求めたい重みの総和になるようにグラフを構築する。
- 辺iが部分グラフに含まれないなら、コストA_i掛かると捉えられる
- 頂点jが部分グラフに含まれるなら、コストW_j掛かると捉えられる
また、ある辺が部分グラフに含まれて、その辺の両端の頂点が含まれない、という事は許されないので、（頂点Sが必ず「部分グラフに含まれる」、頂点Tが必ず「部分グラフに含まれない」とすれば）その2頂点から辺へcapacity=無限の辺を張るようにする。
解答コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
template<class t> using vc=vector<t>;
using ll = long long;
const ll LINF = 1e18;
template <class T>
class Dinic {
private:
const int INF = 1e9;
vector<int> level, itr;
struct Edge {
int to, rev; T cap;
Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
};
vector<vector<Edge>> G;
Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
void bfs(int s) {
level.assign(G.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto &e : G[v]) {
if (level[e.to] < 0 and e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T flow) {
if (v == t) return flow;
for (int &i = itr[v]; i < G[v].size(); i++) {
auto &edge = G[v][i];
if (level[v] < level[edge.to] and edge.cap > 0) {
auto f = dfs(edge.to, t, min(flow, edge.cap));
if (f > 0) {
edge.cap -= f;
get_rev(edge).cap += f;
return f;
}
}
}
return 0;
}
public:
Dinic(int n) { G.resize(n); }
void add_edge(int from, int to, T cap) {
G[from].push_back(Edge(to, (int)G[to].size(), cap));
G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
}
T get_max_flow(int s, int t) {
int n = G.size();
T res = 0;
while (true) {
itr.assign(n, 0);
bfs(s);
if (level[t] < 0) break;
while (true) {
T flow = dfs(s, t, INF);
if (flow > 0) res += flow;
else break;
}
}
return res;
}
};
signed main()
{
cin.tie( 0 ); ios::sync_with_stdio( false );
int n,m; cin>>n>>m;
auto flow=Dinic<ll>(n+m+2);
int s=n+m, t=n+m+1;
rep(i,n){
ll a; cin>>a;
flow.add_edge(s,i,a);
flow.add_edge(i,t,0);
}
ll ans=0;
rep(i,m){
int u,v; ll c; cin>>u>>v>>c;
u--,v--;
ans+=c;
int e=i+n;
flow.add_edge(s,e,0);
flow.add_edge(e,t,c);
flow.add_edge(u,e,LINF);
flow.add_edge(v,e,LINF);
}
ans-=flow.get_max_flow(s,t);
cout<<ans<<endl;
}
RUCPC 2019 Day 1 G イルミネーション
問題
h*wのグリッドが与えられる。各マスには、B[i][j] の得点が配置されており、また (i+j) が偶数のマスにはスイッチがあり、1つのスイッチをONにすると B[i][j]+B[i][j+1]+B[i+1][j]+B[i+1][j+1] の得点が得られるがコストがW掛かる。スイッチのON、OFFを適切に設定した時、得られる得点の最大値を求めよ。
制約
解説
あるマスが2つのスイッチの対象になるなら得点を二重にカウントしないように注意する必要があるが、一旦これを考えないようにすれば、あるスイッチをONにしたとき得られる利得は、max(0, B[i][j]+B[i][j+1]+B[i+1][j]+B[i+1][j+1]-W) となる。全てのスイッチについて、この利得が得られると仮定して、実際には得られない利得の最小値を求めこれを仮定した値から減算することで解を求める。
この問題では、各スイッチについて、ONにするかOFFにするかのS-Tグラフを構築する。あるスイッチをOFFにするなら辺の capacity は上に示した通り max(0, B[i][j]+B[i][j+1]+B[i+1][j]+B[i+1][j+1]-W) となる。また、ある2つのスイッチが共有するマスを持つなら、その2つのスイッチを「両方ONにしたとき共有するマスのスコアだけ罰金」という辺を張りたい。「両方がSに属するとき罰金」はそのままでは扱えないので、偶数行目にあるスイッチと奇数行目にあるスイッチで、頂点S/TのON/OFFを入れ替える。こうすることで、偶数行目にある頂点から奇数行目にある頂点に辺を張ることで、「両方ONのとき共有するマスのスコアだけ罰金」という辺を張ることができる。
解答コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
template<class t> using vc=vector<t>;
using ll = long long;
const ll LINF = 1e18;
template <class T>
class Dinic {
private:
const int INF = 1e9;
vector<int> level, itr;
struct Edge {
int to, rev; T cap;
Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
};
vector<vector<Edge>> G;
Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
void bfs(int s) {
level.assign(G.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto &e : G[v]) {
if (level[e.to] < 0 and e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T flow) {
if (v == t) return flow;
for (int &i = itr[v]; i < G[v].size(); i++) {
auto &edge = G[v][i];
if (level[v] < level[edge.to] and edge.cap > 0) {
auto f = dfs(edge.to, t, min(flow, edge.cap));
if (f > 0) {
edge.cap -= f;
get_rev(edge).cap += f;
return f;
}
}
}
return 0;
}
public:
Dinic(int n) { G.resize(n); }
void add_edge(int from, int to, T cap) {
G[from].push_back(Edge(to, (int)G[to].size(), cap));
G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
}
T get_max_flow(int s, int t) {
int n = G.size();
T res = 0;
while (true) {
itr.assign(n, 0);
bfs(s);
if (level[t] < 0) break;
while (true) {
T flow = dfs(s, t, INF);
if (flow > 0) res += flow;
else break;
}
}
return res;
}
};
int h,w;
int node(int i, int j){
return i*w+j;
}
signed main()
{
cin.tie( 0 ); ios::sync_with_stdio( false );
ll W; cin>>h>>w>>W;
vc<vc<ll>> b(h, vc<ll>(w));
rep(i,h) rep(j,w) cin>>b[i][j];
auto flow=Dinic<ll>(h*w+2);
int s=h*w, t=h*w+1;
ll ans=0;
rep(i,h-1){
rep(j,w-1){
if((i+j)%2==0){
ll sum=0;
sum+=b[i][j];
sum+=b[i][j+1];
sum+=b[i+1][j];
sum+=b[i+1][j+1];
sum-=W;
if(sum>0){
ans+=sum;
}
int now=node(i,j);
if(i%2==0){
flow.add_edge(s,now,max(0LL,sum));
flow.add_edge(now,t,0LL);
if(i+1<h-1 and j+1<w-1){
int nxt=node(i+1,j+1);
flow.add_edge(now,nxt,b[i+1][j+1]);
}
if(i+1<h-1 and j-1>=0){
int nxt=node(i+1,j-1);
flow.add_edge(now,nxt,b[i+1][j]);
}
if(i-1>=0 and j+1<w-1){
int nxt=node(i-1,j+1);
flow.add_edge(now,nxt,b[i][j+1]);
}
if(i-1>=0 and j-1>=0){
int nxt=node(i-1,j-1);
flow.add_edge(now,nxt,b[i][j]);
}
}else{
flow.add_edge(s,now,0LL);
flow.add_edge(now,t,max(0LL,sum));
}
}
}
}
auto res=flow.get_max_flow(s,t);
ans-=res;
cout<<ans<<endl;
}
Google Code Jam 2008 World Finals - The Year of Code Jam
codingcompetitions.withgoogle.com
問題
M*Nのグリッドが与えられ、各マスには、#,.,?のいずれかが記載されている。#マスには初期値として4のスコアが与えられ、上下左右に隣接するマスにある#の数だけスコアが1減算される。各?マスを#、. をいずれかのマスとして適切に割り振ったとき、スコアの合計の最大値を求めよ。
制約
解説
まずスコアが加算される可能性があるマスは?か#のいずれかである。 #の場合は、4-(周囲の#の個数)-(周囲の?のうち#にするものの個数)がそのマスが得るスコアとなり、?マスの場合も自身を#マスとするなら同様となる。 そしていずれの場合でも周囲の?マスは . である場合の方がスコアは大きくなる。 この問題も上述のイルミネーションの解法と同様の方針で、全てのマスについて最大のスコアを得られると仮定して、実際には得られないスコアの最小値を求め減算することで解が得られる。
各?マスについて、#にするか、. にするかで以下の様に変わる。
- #にするなら仮定した値は得られるが、周囲の#の個数*2のスコアが減算される
- .にするなら仮定した値は得られない
また、隣り合う?同士について、「その両方が#になるなら2点減算される」という条件が存在することになる。
「ある2つの要素がどちらともSに属するなら罰金」という条件は扱えないので、これもイルミネーションの時と同様の工夫として、マスの偶奇に応じて、#と.の方向を入れ替えるようにする。これで偶数マスから奇数マスへ辺を張ることで条件を扱えるようになる。
解答コード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
template<class t> using vc=vector<t>;
using ll = long long;
const ll LINF = 1e18;
template <class T>
class Dinic {
private:
const int INF = 1e9;
vector<int> level, itr;
struct Edge {
int to, rev; T cap;
Edge(int to, int rev, T cap) : to(to), rev(rev), cap(cap){};
};
vector<vector<Edge>> G;
Edge &get_rev(Edge &edge) { return G[edge.to][edge.rev]; }
void bfs(int s) {
level.assign(G.size(), -1);
level[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
auto v = q.front();
q.pop();
for (auto &e : G[v]) {
if (level[e.to] < 0 and e.cap > 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T flow) {
if (v == t) return flow;
for (int &i = itr[v]; i < G[v].size(); i++) {
auto &edge = G[v][i];
if (level[v] < level[edge.to] and edge.cap > 0) {
auto f = dfs(edge.to, t, min(flow, edge.cap));
if (f > 0) {
edge.cap -= f;
get_rev(edge).cap += f;
return f;
}
}
}
return 0;
}
public:
Dinic(int n) { G.resize(n); }
void add_edge(int from, int to, T cap) {
G[from].push_back(Edge(to, (int)G[to].size(), cap));
G[to].push_back(Edge(from, (int)G[from].size() - 1, 0));
}
T get_max_flow(int s, int t) {
int n = G.size();
T res = 0;
while (true) {
itr.assign(n, 0);
bfs(s);
if (level[t] < 0) break;
while (true) {
T flow = dfs(s, t, INF);
if (flow > 0) res += flow;
else break;
}
}
return res;
}
};
int h,w;
int node(int i, int j){
return i*w+j;
}
const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};
inline bool inside(int y, int x, int H, int W) {
return (y >= 0 && x >= 0 && y < H && x < W);
}
void solve(int idx){
cin>>h>>w;
vc<vc<int>> G(h,vc<int>(w));
rep(y,h) rep(x,w) {
char c; cin>>c;
if(c=='?') G[y][x]=1;
if(c=='#') G[y][x]=2;
}
ll ans=0;
int s=h*w, t=h*w+1;
auto flow=Dinic<ll>(h*w+2);
rep(y,h){
rep(x,w){
int now=node(y,x);
int score=4;
if(G[y][x]==1){
rep(i,4) {
int ny=y+dy[i], nx=x+dx[i];
if(inside(ny,nx,h,w)){
if(G[ny][nx]==1){
if((y+x)%2==0){
int nxt=node(ny,nx);
flow.add_edge(now,nxt,2);
}
}
if(G[ny][nx]==2){
score-=2;
}
}
}
score=max(0,score);
ans+=score;
if((y+x)%2==0){
flow.add_edge(s,now,score);
flow.add_edge(now,t,0);
}else{
flow.add_edge(s,now,0);
flow.add_edge(now,t,score);
}
}else if(G[y][x]==2){
rep(i,4){
int ny=y+dy[i], nx=x+dx[i];
if(inside(ny,nx,h,w) and G[ny][nx]==2) score--;
}
ans+=score;
}
}
}
ll cost=flow.get_max_flow(s,t);
ans-=cost;
cout<<"Case #"<<idx<<": "<<ans<<endl;
}
signed main()
{
cin.tie( 0 ); ios::sync_with_stdio( false );
int t; cin>>t;
reps(i,t){
solve(i);
}
}
参考
www.slideshare.net
