Submission #1165762
Source Code Expand
#include <iostream>
#include <algorithm>
#include <tuple>
#include <array>
#include <queue>
using namespace std;
using Weight = int;
using Flow = int;
constexpr Flow inf = 1234;
// N E S W
constexpr array<int, 4> dr = {-1, 0, 1, 0},
dc = { 0, 1, 0,-1};
constexpr int dr_size = dr.size();
struct Edge {
int dst, rev;
Flow capa;
Weight cost;
};
struct Graph {
int size;
vector<vector<Edge>> g;
Graph(int size) : size(size) { g.resize(size); }
void add_edge(int src, int dst, Flow capa);
void add_edge(int src, int dst, Flow capa, Weight cost);
Flow max_flow(int s, int t) { throw; }
Flow min_cost_flow_ford(int s, int t, Flow f); // ベルマンフォード
Flow min_cost_flow_dijk(int s, int t, Flow f); // ダイクストラ
};
struct FordFulkerson : Graph {
vector<bool> used;
FordFulkerson(int size) : Graph(size) {}
Flow max_flow(int s, int t);
private:
Flow dfs(int v, int t, Flow flow);
};
struct Dinic : Graph {
vector<int> level, iter;
Dinic(int size) : Graph(size) {}
Flow max_flow(int s, int t);
private:
void bfs(int s);
Flow dfs(int v, int t, Flow flow);
};
void Graph::add_edge(int src, int dst, Flow capa) {
add_edge(src, dst, capa, 0);
}
void Graph::add_edge(int src, int dst, Flow capa, Weight cost) {
g[src].push_back(Edge({dst, int(g[dst].size()), capa, cost}));
g[dst].push_back(Edge({src, int(g[src].size())-1, 0, -cost}));
}
Flow Graph::min_cost_flow_ford(int s, int t, Flow f) {
Flow res = 0;
vector<int> prev_v(size), prev_e(size);
vector<Flow> dist;
while(f > 0) {
dist.assign(size, inf);
dist[s] = 0;
bool update = true;
while(update) {
update = false;
for(int v=0; v<size; ++v) {
if(dist[v] == inf) { continue; }
for(int i=0; i<g[v].size(); ++i) {
Edge& e = g[v][i];
if(e.capa > 0 && dist[e.dst] > dist[v] + e.cost) {
dist[e.dst] = dist[v] + e.cost;
prev_v[e.dst] = v;
prev_e[e.dst] = i;
update = true;
}
}
}
}
if(dist[t] == inf) { return inf; }
Flow d = f;
for(int v=t; v!=s; v=prev_v[v]) {
d = min(d, g[prev_v[v]][prev_e[v]].capa);
}
f -= d;
res += d * dist[t];
for(int v=t; v!=s; v=prev_v[v]) {
Edge& e = g[prev_v[v]][prev_e[v]];
e.capa -= d;
g[v][e.rev].capa += d;
}
}
return res;
}
Flow Graph::min_cost_flow_dijk(int s, int t, Flow f) {
Flow res = 0;
vector<int> prev_v(size), prev_e(size);
vector<int> h(size);
while(f > 0) {
vector<int> dist(size, inf);
dist[s] = 0;
queue<pair<int, int>> que;
// 最短距離、番号
que.emplace(0, s);
while(!que.empty()) {
int c, v; tie(c, v) = que.front(); que.pop();
if(dist[v] < c) { continue; }
for(int i=0; i<g[v].size(); ++i) {
Edge& e = g[v][i];
if(e.capa > 0 && dist[e.dst] > dist[v] + e.cost + h[v] - h[e.dst]) {
dist[e.dst] = dist[v] + e.cost + h[v] - h[e.dst];
prev_v[e.dst] = v;
prev_e[e.dst] = i;
que.emplace(dist[e.dst], e.dst);
}
}
}
if(dist[t] == inf) { return inf; }
for(int v=0; v<size; ++v) { h[v] += dist[v]; }
Flow d = f;
for(int v=t; v!=s; v=prev_v[v]) {
d = min(d, g[prev_v[v]][prev_e[v]].capa);
}
f -= d;
res += d * h[t];
for(int v=t; v!=s; v=prev_v[v]) {
Edge& e = g[prev_v[v]][prev_e[v]];
e.capa -= d;
g[v][e.rev].capa += d;
}
}
return res;
}
Flow FordFulkerson::max_flow(int s, int t) {
Flow res = 0;
while(true) {
used.assign(size, false);
Flow flow = dfs(s, t, inf);
if(flow == 0) { return res; }
res += flow;
if(res >= inf) { return inf; }
}
}
Flow FordFulkerson::dfs(int v, int t, Flow flow) {
if(v == t) { return flow; }
used[v] = true;
for(Edge& e : g[v]) {
if(used[e.dst] || e.capa <= 0) { continue; }
int d = dfs(e.dst, t, min(flow, e.capa));
if(d > 0) {
e.capa -= d;
g[e.dst][e.rev].capa += d;
return d;
}
}
return 0;
}
void Dinic::bfs(int s) {
level.assign(size, -1);
queue<int> que;
level[s] = 0;
que.push(s);
while(!que.empty()) {
int v = que.front(); que.pop();
for(Edge& e : g[v]) {
if(e.capa > 0 && level[e.dst] < 0) {
level[e.dst] = level[v] + 1;
que.push(e.dst);
}
}
}
}
Flow Dinic::dfs(int v, int t, Flow flow) {
if(v == t) { return flow; }
for(int& i=iter[v]; i<g[v].size(); ++i) {
Edge& e = g[v][i];
if(e.capa <= 0 || level[v] >= level[e.dst]) { continue; }
Flow d = dfs(e.dst, t, min(flow, e.capa));
if(d > 0) {
e.capa -= d;
g[e.dst][e.rev].capa += d;
return d;
}
}
return 0;
}
Flow Dinic::max_flow(int s, int t) {
Flow res = 0;
while(true) {
bfs(s);
if(level[t] < 0) { return res; }
iter.assign(size, 0);
Flow flow;
while((flow = dfs(s, t, inf)) > 0) {
res += flow;
if(res >= inf) { return inf; }
}
}
}
int main(void) {
int R, C; cin >> R >> C;
vector<string> G(R);
for(int r=0; r<R; ++r) { cin >> G[r]; }
Dinic graph(R*C*2 + 2);
int s = R * C * 2,
t = s + 1;
for(int r=0; r<R; ++r) {
for(int c=0; c<C; ++c) {
int p = r * C + c,
q = p + R * C;
if(G[r][c] == 'X') {
graph.add_edge(p, q, inf);
graph.add_edge(s, p, inf);
} else {
graph.add_edge(p, q, 1);
}
for(int i=0; i<dr_size; ++i) {
int nr = r + dr[i],
nc = c + dc[i];
if(0 <= nr && nr < R && 0 <= nc && nc < C) { // (r, c) は端ではない
int np = nr * C + nc,
nq = np + R * C;
graph.add_edge(q, np, inf);
} else { // (r, c) は端である
graph.add_edge(q, t, inf);
}
}
}
}
Flow res = graph.max_flow(s, t);
if(res >= inf) { res = -1; }
cout << res << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Fences |
User |
qiaoranliqu |
Language |
C++14 (GCC 5.4.1) |
Score |
150 |
Code Size |
6245 Byte |
Status |
AC |
Exec Time |
42 ms |
Memory |
3836 KB |
Judge Result
Set Name |
All |
Score / Max Score |
150 / 150 |
Status |
|
Set Name |
Test Cases |
All |
00_sample.txt, 01_sample.txt, 02_sample.txt, 10_rand_00.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 11_hashi_00.txt, 11_hashi_01.txt, 11_hashi_02.txt, 12_rect_00.txt, 12_rect_01.txt, 12_rect_02.txt, 99_all_one.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample.txt |
AC |
1 ms |
256 KB |
01_sample.txt |
AC |
1 ms |
256 KB |
02_sample.txt |
AC |
1 ms |
256 KB |
10_rand_00.txt |
AC |
1 ms |
256 KB |
10_rand_01.txt |
AC |
2 ms |
384 KB |
10_rand_02.txt |
AC |
11 ms |
1408 KB |
10_rand_03.txt |
AC |
12 ms |
1280 KB |
10_rand_04.txt |
AC |
9 ms |
3456 KB |
10_rand_05.txt |
AC |
14 ms |
3584 KB |
10_rand_06.txt |
AC |
7 ms |
1280 KB |
10_rand_07.txt |
AC |
13 ms |
2304 KB |
10_rand_08.txt |
AC |
25 ms |
3200 KB |
11_hashi_00.txt |
AC |
4 ms |
1792 KB |
11_hashi_01.txt |
AC |
3 ms |
896 KB |
11_hashi_02.txt |
AC |
4 ms |
1920 KB |
12_rect_00.txt |
AC |
42 ms |
3072 KB |
12_rect_01.txt |
AC |
7 ms |
896 KB |
12_rect_02.txt |
AC |
9 ms |
2688 KB |
99_all_one.txt |
AC |
8 ms |
3836 KB |