提出 #16973807

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <assert.h>
#include <cmath>
#include <stack>
#include <deque>
#include <set>
#include <unordered_map>
#include <complex>
#include <fstream>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
using ll = long long;
const int mxn = 2510;
const int inf = 1e9;
char matrix[mxn][mxn];

vector<int> adj[mxn];
int cost[mxn][mxn], capacity[mxn][mxn], d[mxn], p[mxn];

const int INF = 1e9;

void shortest_paths(int n, int v0) {
    for(int i=0; i<n; i++) d[i] = INF;
    d[v0] = 0;
    vector<bool> inq(n, false);
    queue<int> q;
    q.push(v0);
    for(int i=0; i<n; i++) p[i] = -1;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int v : adj[u]) {
            if (capacity[u][v] > 0 && d[v] > d[u] + cost[u][v]) {
                d[v] = d[u] + cost[u][v];
                p[v] = u;
                if (!inq[v]) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int min_cost_flow(int N, int K, int s, int t) {
    int flow = 0;
    int cost = 0;
    while (flow < K) {
        shortest_paths(N, s);
        if (d[t] == INF)
            break;

        // find max flow on that path
        int f = K - flow;
        int cur = t;
        while (cur != s) {
            f = min(f, capacity[p[cur]][cur]);
            cur = p[cur];
        }

        // apply flow
        flow += f;
        cost += f * d[t];
        cur = t;
        while (cur != s) {
            capacity[p[cur]][cur] -= f;
            capacity[cur][p[cur]] += f;
            cur = p[cur];
        }
    }

    if (flow < K)
        return -1;
    else
        return cost;
}

void add_edge(int from, int to, int cap, int co) {
	adj[from].push_back(to); adj[to].push_back(from);
	capacity[from][to] = cap; 
	cost[from][to] = co;
	cost[to][from] = -co;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n, m; cin>>n>>m;
	for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin>>matrix[i][j];

	int s = m*n, t = m*n+1, cnt = 0;
	for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(matrix[i][j]=='o') add_edge(s, i*m+j, 1, 0), cnt++;
	for(int i=0; i<n; i++) for(int j=0; j<m; j++) if(matrix[i][j]=='o' or matrix[i][j]=='.') add_edge(i*m+j, t, 1, 0);
	for(int i=0; i<n; i++) for(int j=0; j<m; j++) {
		if(i+1<n and matrix[i][j]!='#' and matrix[i+1][j]!='#') add_edge(i*m+j, i*m+j+m, inf, -1);
		if(j+1<m and matrix[i][j]!='#' and matrix[i][j+1]!='#') add_edge(i*m+j, i*m+j+1, inf, -1);
	}

	cout << -min_cost_flow(n*m+2, cnt, s, t) << '\n';
	return 0;
}
//comparator function in sorting
//swapping arguments
//missing cases in dp
//dividing in modulo
//Beware of overflow and modulo
//Be mindful of overflow
//s is a matrix but forget
//length of ranges
//working with bit using ull

提出情報

ジャッジ結果