QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#583814#9224. Express EvictionBerryPieTL 1ms4252kbC++202.7kb2024-09-22 22:46:092024-09-22 22:46:11

Judging History

你现在查看的是最新测评结果

  • [2024-09-22 22:46:11]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4252kb
  • [2024-09-22 22:46:09]
  • 提交

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 = 500+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: 1ms
memory: 4252kb

input:

4 6
.##...
.#....
##....
....#.

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: -100
Time Limit Exceeded

input:

20 30
...###########################
#..###########################
...###########################
...###########################
.#############################
...###########################
...###########################
#..###########################
...###########################
..#...............

output:


result: