QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#583815 | #9224. Express Eviction | BerryPie | WA | 2ms | 8508kb | C++20 | 2.7kb | 2024-09-22 22:48:38 | 2024-09-22 22:48:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct Edge{
int u, v, nxt, cap, flow;
Edge(int u = 0, int v = 0, int nxt = 0, int cap = 0, int flow = 0):
u(u), v(v), nxt(nxt), cap(cap), flow(flow){}
};
const int MAXN = 50+5;
const int MAX = 5000+5;
const int inf = 1e9;
int n, m, cnt, tot, s, t;
int a[MAXN][MAXN], id[MAXN][MAXN][2];
int head[MAX], d[MAX], cur[MAX], vis[MAX];
Edge G[MAX*50];
void add_edge(int from, int to, int cap){
G[++cnt] = Edge(from, to, head[from], cap, 0); head[from] = cnt;
G[++cnt] = Edge(to, from, head[to], 0, 0); head[to] = cnt;
}
int bfs(){
for(int i = 1; i <= tot; i++) vis[i] = 0;
queue<int> que;
que.push(s);
d[s] = 0;
vis[s] = true;
while(!que.empty()){
int u = que.front(); que.pop();
for(int e = head[u]; e; e = G[e].nxt){
int v = G[e].v;
if(!vis[v] && G[e].cap > G[e].flow){
vis[v] = true;
d[v] = d[u] + 1;
que.push(v);
}
}
}
return vis[t];
}
int dfs(int u, int a){
if(u == t || a == 0) return a;
int flow = 0, f;
for(int &e = cur[u]; e; e = G[e].nxt){
int v = G[e].v;
if(d[v] == d[u]+1 && (f = dfs(v, min(a, G[e].cap - G[e].flow))) > 0){
G[e].flow += f;
G[e^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int maxflow(){
int flow = 0;
while(bfs()){
for(int i = 1; i <= tot; i++) cur[i] = head[i];
flow += dfs(s, inf);
}
return flow;
}
int main(){
cin >> n >> m;
s = ++tot;
t = ++tot;
for(int i = 1; i <= n; i++){
string s;
cin >> s;
s = ' ' + s;
for(int j = 1; j <= m; j++){
a[i][j] = s[j] == '#';
id[i][j][0] = ++tot;
id[i][j][1] = ++tot;
}
}
cnt = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j]){
add_edge(id[i][j][0], id[i][j][1], 1);
if(j == 1 || i == n){
add_edge(s, id[i][j][0], inf);
}
if(j == m || i == 1){
add_edge(id[i][j][1], t, inf);
}
for(int i1 = 0; i1 <= 2; i1++){
for(int j1 = 0; j1 <= 2; j1++){
if(i1 == 0 && j1 == 0) continue;
if(i-i1 < 1 || j+j1 > m || !a[i-i1][j+j1]) continue;
add_edge(id[i][j][1], id[i-i1][j+j1][0], inf);
}
}
}
}
}
cout << maxflow() << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 8508kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 8472kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
10
result:
wrong answer 1st numbers differ - expected: '11', found: '10'