Submission #1271927
Source Code Expand
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<class V> struct MaxFlow {
struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} };
int MV; vector<vector<edge>> E; vector<int> itr, lev;
MaxFlow() {} MaxFlow(int n) { init(n); }
void init(int n) { MV = n; itr = vector<int>(MV), lev = vector<int>(MV); E = vector<vector<edge>>(MV); }
void add_edge(int x, int y, V cap, bool undir = false) { E[x].push_back(edge(y, (int)E[y].size(), cap));
E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0)); }
void bfs(int cur) { rep(i, 0, MV) lev[i] = -1; queue<int> q; lev[cur] = 0; q.push(cur);
while (q.size()) { int v = q.front(); q.pop();
for(auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to); } }
V dfs(int from, int to, V cf) { if (from == to) return cf;
for (; itr[from]<E[from].size(); itr[from]++) {
edge* e = &E[from][itr[from]]; if (e->cap>0 && lev[from]<lev[e->to]) {
V f = dfs(e->to, to, min(cf, e->cap));
if (f>0) { e->cap -= f; E[e->to][e->reve].cap += f; return f; }
} } return 0; }
V maxflow(int from, int to) { V fl = 0, tf;
while (1) { bfs(from); if (lev[to]<0) return fl;
rep(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf; } }
};
/*---------------------------------------------------------------------------------------------------
∧_∧
∧_∧ (´<_` ) Welcome to My Coding Space!
( ´_ゝ`) / ⌒i
/ \ | |
/ / ̄ ̄ ̄ ̄/ |
__(__ニつ/ _/ .| .|____
\/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/
#define INF 100000
int H, W; string S[101];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> H >> W;
rep(y, 0, H) cin >> S[y];
int N = H * W;
MaxFlow<int> mf(N * 2 + 2);
int s = N * 2, t = N * 2 + 1;
rep(y, 0, H) rep(x, 0, W) {
if (S[y][x] == 'X') {
mf.add_edge(y * W + x, y * W + x + N, INF);
mf.add_edge(s, y * W + x, INF);
}
else mf.add_edge(y * W + x, y * W + x + N, 1);
}
rep(y, 0, H) rep(x, 0, W) rep(i, 0, 4) {
int xx = x + dx[i];
int yy = y + dy[i];
int a = y * W + x;
int b = yy * W + xx;
if (xx < 0 || W <= xx || yy < 0 || H <= yy) mf.add_edge(a + N, t, INF);
else {
mf.add_edge(a + N, b, 1);
if(S[y][x] == '.') mf.add_edge(a + N, b, INF);
}
}
int f = mf.maxflow(s, t);
if (INF <= f) f = -1;
cout << f << endl;
}
Submission Info
Submission Time |
|
Task |
E - Fences |
User |
hamayanhamayan |
Language |
C++14 (GCC 5.4.1) |
Score |
150 |
Code Size |
3298 Byte |
Status |
AC |
Exec Time |
64 ms |
Memory |
4096 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 |
16 ms |
1664 KB |
10_rand_03.txt |
AC |
18 ms |
1664 KB |
10_rand_04.txt |
AC |
9 ms |
2944 KB |
10_rand_05.txt |
AC |
17 ms |
3840 KB |
10_rand_06.txt |
AC |
10 ms |
1664 KB |
10_rand_07.txt |
AC |
19 ms |
2816 KB |
10_rand_08.txt |
AC |
38 ms |
4096 KB |
11_hashi_00.txt |
AC |
21 ms |
2304 KB |
11_hashi_01.txt |
AC |
7 ms |
1152 KB |
11_hashi_02.txt |
AC |
7 ms |
2560 KB |
12_rect_00.txt |
AC |
64 ms |
3712 KB |
12_rect_01.txt |
AC |
10 ms |
1152 KB |
12_rect_02.txt |
AC |
10 ms |
2432 KB |
99_all_one.txt |
AC |
8 ms |
3328 KB |