Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- #define endl '\n'
- const int N = 5e3 + 10;
- const int INF = 0x3f3f3f3f;
- class Dinic_ssp {
- private:
- struct Edge {
- int from, to, cap, flow, val;
- Edge (int u, int v, int c, int f, int vl) :
- from(u), to(v), cap(c), flow(f), val(vl) {}
- };
- vector<Edge> edges;
- vector<int> g[N];
- int dis[N], cur[N], mincost;
- bool vis[N];
- public:
- void init (int n) {
- for (int i = 1; i <= n; i ++) {
- g[i].clear();
- }
- edges.clear();
- mincost = 0;
- }
- void addEdge (int u, int v, int c, int w) {
- edges.push_back({u, v, c, 0, w});
- edges.push_back({v, u, 0, 0, -w});
- int m = edges.size();
- g[u].push_back(m - 2);
- g[v].push_back(m - 1);
- }
- bool spfa (int s, int t) {
- memset(dis, 0x3f, sizeof dis);
- memset(cur, 0, sizeof cur);
- queue<int> q;
- dis[s] = 0;
- q.push(s);
- vis[s] = 1;
- while (!q.empty()) {
- int x = q.front();
- q.pop();
- vis[x] = 0;
- // cout << x << ' ' << dis[x] << endl;
- for (auto &i: g[x]) {
- Edge &e = edges[i];
- if (e.cap > e.flow && dis[e.to] > dis[x] + e.val) {
- dis[e.to] = dis[x] + e.val;
- if (!vis[e.to]) {
- q.push(e.to);
- vis[e.to] = 1;
- }
- }
- }
- }
- return dis[t] != INF;
- }
- int dfs (int x, int t, int flow) {
- if (x == t || flow == 0) return flow;
- int res = 0;
- vis[x] = 1;
- for (int i = cur[x]; i < (int)g[x].size(); i ++) {
- cur[x] = i;
- Edge &e = edges[g[x][i]];
- if (dis[e.to] == dis[x] + e.val && !vis[e.to]) {
- int d = dfs(e.to, t, min(flow - res, e.cap - e.flow));
- res += d;
- mincost += d * e.val;
- edges[g[x][i]].flow += d;
- edges[g[x][i] ^ 1].flow -= d;
- if (res == flow) {
- vis[x] = 0;
- return flow;
- }
- }
- }
- vis[x] = 0;
- return res;
- }
- pair<int, int> mcmf (int s, int t) {
- int flow = 0;
- while (spfa(s, t)) {
- while (int d = dfs(s, t, INF)) {
- flow += d;
- }
- }
- return {flow, mincost};
- }
- };
- Dinic_ssp dinic;
- int n, m, sz;
- int mp[50][50];
- int dx[2] = {0, 1};
- int dy[2] = {1, 0};
- int get_id(int x, int y, int k) {
- return (x - 1) * m + y + k * n * m;
- }
- bool check (int x, int y) {
- return (x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != 1);
- }
- void solve() {
- cin >> sz >> n >> m;
- int s = 0, t = 2 * n * m + 1;
- dinic.init(t);
- dinic.addEdge(s, get_id(1, 1, 0), sz, 0);
- dinic.addEdge(get_id(n, m, 1), t, sz, 0);
- for (int i = 1; i <= n; i ++) {
- for (int j = 1; j <= m; j ++) {
- cin >> mp[i][j];
- }
- }
- for (int i = 1; i <= n; i ++) {
- for (int j = 1; j <= m; j ++) {
- if (mp[i][j] == 1) continue;
- if (mp[i][j] == 2) dinic.addEdge(get_id(i, j, 0), get_id(i, j, 1), 1, -1);
- dinic.addEdge(get_id(i, j, 0), get_id(i, j, 1), INF, 0);
- for (int k = 0; k < 2; k ++) {
- int nx = i + dx[k];
- int ny = j + dy[k];
- if (check(nx, ny)) {
- // cout << i << ',' << j << " -> " << nx << ',' << ny << endl;
- dinic.addEdge(get_id(i, j, 1), get_id(nx, ny, 0), INF, 0);
- }
- }
- }
- }
- auto res = dinic.mcmf(s, t);
- cout << res.first << ' ' << res.second << endl;
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- int _ = 1;
- // cin >> _;
- while (_--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement