QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#545018#9224. Express EvictionAshbourneWA 2ms4340kbC++142.3kb2024-09-02 21:50:042024-09-02 21:50:05

Judging History

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

  • [2024-09-02 21:50:05]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4340kb
  • [2024-09-02 21:50:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
class Dinic{
	private:
		struct Edge{
			int to, rev, cap;
		};
		vector<vector<Edge>> graph;
		vector<vector<Edge>::iterator> cur;
		vector<int> dist;
		queue<int> que;
		int n, S, T;
		bool bfs(void){
			for(int i = 1; i <= n; ++ i) cur[i] = graph[i].begin(), dist[i] = INT_MAX;
			dist[S] = 0; que.push(S);
			while(!que.empty()){
				int p = que.front();
				que.pop();
				for(auto i : graph[p])
					if(i.cap && dist[i.to] > dist[p] + 1)
						dist[i.to] = dist[p] + 1, que.push(i.to);
			}
			return dist[T] != INT_MAX;
		}
		int dfs(int p, int rest){
			if(p == T || !rest) return rest;
			int c, used = 0;
			for(auto i = cur[p]; i != graph[p].end() && rest; ++ i){
				cur[p] = i;
				if(!i->cap || dist[i->to] != dist[p] + 1) continue;
				if(!(c = dfs(i->to, min(rest, i->cap)))) dist[i->to] = -1;
				i->cap -=c; graph[i->to][i->rev].cap += c, used += c, rest -= c;
			}
			return used;
		}
	public:
		void resize(int _n) {return n = _n, graph.resize(n + 1), cur.resize(n + 1), dist.resize(n + 1);}
		void addEdge(int from, int to, int cap){
			return graph[from].push_back(Edge{to, (int)graph[to].size(), cap}),
				   graph[to].push_back(Edge{to, (int)graph[from].size() - 1, 0});

		}
		int maxflow(int _S, int _T){
			S = _S, T = _T;
			int ans = 0;
			while(bfs()) ans += dfs(S, INF);
			return ans;
		}
};
int a[55][55];
int main(){
	ios::sync_with_stdio(0);
	int n, m;
	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;
		}
	int base = n * m, S = 2 * base + 1, T = 2 * base + 2;
	Dinic dnc;
	dnc.resize(T);
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= m; ++ j){
			int p = (i - 1) * m + j;
			dnc.addEdge(p, base + p, 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 || dx > n || dy < 1 || dy > m || !a[dx][dy]) continue;
					int q = (dx - 1) * m + dy;
					if(p < q) dnc.addEdge(p + base, q, INF), dnc.addEdge(q + base, p, INF);
				}
			if(i == n || j == 1) dnc.addEdge(S, p, INF);
			if(i == 1 || j == m) dnc.addEdge(base + p, T, INF);
		}
	cout << dnc.maxflow(S, T) << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 4340kb

input:

35 35
....###########...#########........
##..#######################..#####.
....#######################..#####.
...#.....##################..#####.
.##......##################.....##.
.##..##..#############.....#....##.
.....##..#############......##..##.
....#....#############..##..##..##.
####.....

output:

13

result:

wrong answer 1st numbers differ - expected: '16', found: '13'