QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#544152 | #9224. Express Eviction | Ashbourne | TL | 0ms | 3788kb | C++14 | 3.1kb | 2024-09-02 10:30:47 | 2024-09-02 10:30:47 |
Judging History
answer
#include<bits/stdc++.h>
const int N = 10005;
const int INF = 0x3f3f3f3f;
using namespace std;
int s, t, tot, cnt;
struct Edge{
int next, to, cap, flow;
}edge[N * 100];
int head[N];
void add(int u, int v, int w, int rw = 0){
edge[++tot] = {head[u], v, w, 0};
head[u] = tot;
edge[++tot] = {head[v], u, 0, 0};
head[v] = tot;
}
int maxflow = 0;
int dep[N], cur[N];
bool bfs(){
queue<int> q;
memset(dep, 0, sizeof (dep[0]) * (cnt + 1));
dep[s] = 1;
q.push(s);
while(q.size()){
int u = q.front();
q.pop();
for(int i = head[u]; i; i = edge[i].next){
int v = edge[i].to;
if((!dep[v]) && (edge[i].cap > edge[i].flow)){
dep[v] = dep[u] + 1;
if(v == t) return 1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u, int flow){
if((u == t) || (!flow)) return flow;
int ret = 0;
for(int &i = cur[u]; i; i = edge[i].next){
int v = edge[i].to, d;
if(dep[v] != dep[u] + 1) continue;
d = dfs(v, min(flow - ret, edge[i].cap - edge[i].flow));
if(d){
ret += d;
edge[i].flow += d;
edge[i ^ 1].flow -= d;
if(ret == flow) return ret;
}
}
return ret;
}
void dinic(){
while(bfs()){
memcpy(cur, head, sizeof (head[0]) * (cnt + 1));
maxflow += dfs(s, INF);
}
}
int n, m, a[55][55];
void solve(){
memset(head, 0, sizeof head);
cin >> n >> m;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j){
char ch; cin >> ch;
if(ch == '#') a[i][j] = 1;
}
s = 1; t = 2;
maxflow = 0;
// I have deleted some codes about building the graph
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j){
int tem = (i - 1) * m + j + 2;
//cout << tem << endl;
add(tem, tem + n * m, 1);
if(!a[i][j]) continue;
for(int dx = i - 2; dx <= i + 2; ++ dx)
for(int dy = j - 2; dy <= j + 2; ++ dy){
if(dx < 1 || dy < 1 || dx > n || dy > m || !a[dx][dy])continue;
int now = (dx - 1) * m + dy + 2;
if(tem < now) add(now + n * m, tem, INF), add(tem + n * m, now, INF);
}
if(i == n || j == 1) add(s, tem, INF);
if(i == 1 || j == m) add(tem + n * m, t, INF);
}
cnt = 2 + 2 * n * m;
dinic();
cout << maxflow << endl;
}
int main(){
ios::sync_with_stdio(false);
int T = 1;
// cin >> T;
while(T--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Time Limit Exceeded
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............