QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#544152#9224. Express EvictionAshbourneTL 0ms3788kbC++143.1kb2024-09-02 10:30:472024-09-02 10:30:47

Judging History

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

  • [2024-09-02 10:30:47]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3788kb
  • [2024-09-02 10:30:47]
  • 提交

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();
        }
}

詳細信息

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
...###########################
#..###########################
...###########################
...###########################
.#############################
...###########################
...###########################
#..###########################
...###########################
..#...............

output:


result: