Advertisement
wym1111

Untitled

Apr 25th, 2024
601
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. #define endl '\n'
  6. const int N = 5e3 + 10;
  7. const int INF = 0x3f3f3f3f;
  8.  
  9. class Dinic_ssp {
  10. private:
  11.     struct Edge {
  12.         int from, to, cap, flow, val;
  13.         Edge (int u, int v, int c, int f, int vl) :
  14.         from(u), to(v), cap(c), flow(f), val(vl) {}
  15.     };
  16.     vector<Edge> edges;
  17.     vector<int> g[N];
  18.     int dis[N], cur[N], mincost;
  19.     bool vis[N];
  20.    
  21. public:
  22.     void init (int n) {
  23.         for (int i = 1; i <= n; i ++) {
  24.             g[i].clear();
  25.         }
  26.         edges.clear();
  27.         mincost = 0;
  28.     }
  29.     void addEdge (int u, int v, int c, int w) {
  30.         edges.push_back({u, v, c, 0, w});
  31.         edges.push_back({v, u, 0, 0, -w});
  32.         int m = edges.size();
  33.         g[u].push_back(m - 2);
  34.         g[v].push_back(m - 1);
  35.     }
  36.     bool spfa (int s, int t) {
  37.         memset(dis, 0x3f, sizeof dis);
  38.         memset(cur, 0, sizeof cur);
  39.         queue<int> q;
  40.         dis[s] = 0;
  41.         q.push(s);
  42.         vis[s] = 1;
  43.         while (!q.empty()) {
  44.             int x = q.front();
  45.             q.pop();
  46.             vis[x] = 0;
  47. //          cout << x << ' ' << dis[x] << endl;
  48.             for (auto &i: g[x]) {
  49.                 Edge &e = edges[i];
  50.                 if (e.cap > e.flow && dis[e.to] > dis[x] + e.val) {
  51.                     dis[e.to] = dis[x] + e.val;
  52.                     if (!vis[e.to]) {
  53.                         q.push(e.to);
  54.                         vis[e.to] = 1;
  55.                     }
  56.                 }
  57.             }
  58.         }
  59.         return dis[t] != INF;
  60.     }
  61.     int dfs (int x, int t, int flow) {
  62.         if (x == t || flow == 0) return flow;
  63.         int res = 0;
  64.         vis[x] = 1;
  65.         for (int i = cur[x]; i < (int)g[x].size(); i ++) {
  66.             cur[x] = i;
  67.             Edge &e = edges[g[x][i]];
  68.             if (dis[e.to] == dis[x] + e.val && !vis[e.to]) {
  69.                 int d = dfs(e.to, t, min(flow - res, e.cap - e.flow));
  70.                 res += d;
  71.                 mincost += d * e.val;
  72.                 edges[g[x][i]].flow += d;
  73.                 edges[g[x][i] ^ 1].flow -= d;
  74.                 if (res == flow) {
  75.                     vis[x] = 0;
  76.                     return flow;
  77.                 }
  78.             }
  79.         }
  80.         vis[x] = 0;
  81.         return res;
  82.     }
  83.     pair<int, int> mcmf (int s, int t) {
  84.         int flow = 0;
  85.         while (spfa(s, t)) {
  86.             while (int d = dfs(s, t, INF)) {
  87.                 flow += d;
  88.             }
  89.         }
  90.         return {flow, mincost};
  91.     }
  92. };
  93. Dinic_ssp dinic;
  94.  
  95. int n, m, sz;
  96. int mp[50][50];
  97. int dx[2] = {0, 1};
  98. int dy[2] = {1, 0};
  99.  
  100. int get_id(int x, int y, int k) {
  101.     return (x - 1) * m + y + k * n * m;
  102. }
  103. bool check (int x, int y) {
  104.     return (x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != 1);
  105. }
  106.  
  107. void solve() {
  108.     cin >> sz >> n >> m;
  109.     int s = 0, t = 2 * n * m + 1;
  110.     dinic.init(t);
  111.     dinic.addEdge(s, get_id(1, 1, 0), sz, 0);
  112.     dinic.addEdge(get_id(n, m, 1), t, sz, 0);
  113.     for (int i = 1; i <= n; i ++) {
  114.         for (int j = 1; j <= m; j ++) {
  115.             cin >> mp[i][j];
  116.         }
  117.     }
  118.     for (int i = 1; i <= n; i ++) {
  119.         for (int j = 1; j <= m; j ++) {
  120.             if (mp[i][j] == 1) continue;
  121.             if (mp[i][j] == 2) dinic.addEdge(get_id(i, j, 0), get_id(i, j, 1), 1, -1);
  122.             dinic.addEdge(get_id(i, j, 0), get_id(i, j, 1), INF, 0);
  123.             for (int k = 0; k < 2; k ++) {
  124.                 int nx = i + dx[k];
  125.                 int ny = j + dy[k];
  126.                 if (check(nx, ny)) {
  127. //                  cout << i << ',' << j << " -> " << nx << ',' << ny << endl;
  128.                     dinic.addEdge(get_id(i, j, 1), get_id(nx, ny, 0), INF, 0);
  129.                 }
  130.             }
  131.         }
  132.     }
  133.     auto res = dinic.mcmf(s, t);
  134.     cout << res.first << ' ' << res.second << endl;
  135. }
  136.  
  137. signed main() {
  138.     ios::sync_with_stdio(false);
  139.     cin.tie(0), cout.tie(0);
  140.     int _ = 1;
  141. //  cin >> _;
  142.     while (_--){
  143.         solve();
  144.     }
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement