fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 2207;
  9. const ll INF = 1e18;
  10.  
  11. struct Dinic {
  12.     struct Edge {
  13.         int to;
  14.         int rev;
  15.         ll cap;
  16.     };
  17.     int n;
  18.     vector < vector < Edge >> g;
  19.     vector < int > lvl, it;
  20.  
  21.     // Mảng lưu cạnh gốc (khi người dùng gọi add_edge)
  22.     struct Orig {
  23.         int u, v;
  24.         ll cap;
  25.         int g_index;
  26.     };
  27.     vector < Orig > orig_edges;
  28.  
  29.     Dinic(int n = 0): n(n), g(n), lvl(n), it(n) {}
  30.     void reset(int _n) {
  31.         n = _n;
  32.         g.assign(n, {});
  33.         lvl.assign(n, 0);
  34.         it.assign(n, 0);
  35.         orig_edges.clear();
  36.     }
  37.  
  38.     // add_edge: giờ trả về index của cạnh gốc (nếu cần)
  39.     int add_edge(int u, int v, ll c) {
  40.         // trước khi push, index trong g[u] sẽ là g[u].size()
  41.         int idx_in_gu = (int) g[u].size();
  42.         Edge a {
  43.             v,
  44.             (int) g[v].size(),
  45.             c
  46.         };
  47.         Edge b {
  48.             u,
  49.             (int) g[u].size(),
  50.             0
  51.         };
  52.         g[u].push_back(a);
  53.         g[v].push_back(b);
  54.  
  55.         // lưu thông tin cạnh gốc (forward). Trả về id (index trong orig_edges)
  56.         Orig o;
  57.         o.u = u;
  58.         o.v = v;
  59.         o.cap = c;
  60.         o.g_index = idx_in_gu;
  61.         orig_edges.push_back(o);
  62.         return (int) orig_edges.size() - 1;
  63.     }
  64.  
  65.     bool bfs(int s, int t) {
  66.         fill(lvl.begin(), lvl.end(), -1);
  67.         queue < int > q;
  68.         q.push(s);
  69.         lvl[s] = 0;
  70.         while (!q.empty()) {
  71.             int v = q.front();
  72.             q.pop();
  73.             for (auto & e: g[v])
  74.                 if (e.cap > 0 && lvl[e.to] == -1) {
  75.                     lvl[e.to] = lvl[v] + 1;
  76.                     q.push(e.to);
  77.                 }
  78.         }
  79.         return lvl[t] != -1;
  80.     }
  81.     ll dfs(int v, int t, ll f) {
  82.         if (v == t || f == 0) return f;
  83.         for (int & i = it[v]; i < (int) g[v].size(); ++i) {
  84.             Edge & e = g[v][i];
  85.             if (e.cap > 0 && lvl[e.to] == lvl[v] + 1) {
  86.                 ll ret = dfs(e.to, t, min(f, e.cap));
  87.                 if (ret > 0) {
  88.                     e.cap -= ret;
  89.                     g[e.to][e.rev].cap += ret;
  90.                     return ret;
  91.                 }
  92.             }
  93.         }
  94.         return 0;
  95.     }
  96.     ll maxflow(int s, int t) {
  97.         ll flow = 0;
  98.         while (bfs(s, t)) {
  99.             fill(it.begin(), it.end(), 0);
  100.             while (true) {
  101.                 ll pushed = dfs(s, t, INF);
  102.                 if (!pushed) break;
  103.                 flow += pushed;
  104.             }
  105.         }
  106.         return flow;
  107.     }
  108.     vector < char > min_cut_s_side(int s) {
  109.         vector < char > vis(n, 0);
  110.         queue < int > q;
  111.         q.push(s);
  112.         vis[s] = 1;
  113.         while (!q.empty()) {
  114.             int v = q.front();
  115.             q.pop();
  116.             for (auto & e: g[v])
  117.                 if (e.cap > 0 && !vis[e.to]) {
  118.                     vis[e.to] = 1;
  119.                     q.push(e.to);
  120.                 }
  121.         }
  122.         return vis; // vis[u]==1 <=> u in S side
  123.     }
  124.  
  125.     // --------- Hàm truy vết các cạnh thuộc min-cut ----------
  126.     // Trả về vector các tuple: (u, v, cap_original, flow_sent)
  127.     vector < tuple < int, int, ll, ll >> get_min_cut_edges(int s) {
  128.         auto sides = min_cut_s_side(s);
  129.         vector < tuple < int, int, ll, ll >> res;
  130.         for (auto & oe: orig_edges) {
  131.             int u = oe.u;
  132.             int v = oe.v;
  133.             ll cap_orig = oe.cap;
  134.             int idx = oe.g_index;
  135.             // cap hiện tại của forward edge là g[u][idx].cap
  136.             // flow = cap_orig - residual_cap_forward
  137.             if (idx < 0 || idx >= (int) g[u].size()) {
  138.                 // an toàn: phòng trường hợp lỗi lưu vị trí (không nên xảy ra nếu reset/khởi tạo đúng)
  139.                 continue;
  140.             }
  141.             ll residual_cap = g[u][idx].cap;
  142.             ll flow_sent = cap_orig - residual_cap;
  143.  
  144.             // cạnh nằm trong cut nếu u in S và v in T (reachable từ s hoặc không)
  145.             if (sides[u] && !sides[v]) {
  146.                 res.emplace_back(u, v, cap_orig, flow_sent);
  147.             }
  148.         }
  149.         return res;
  150.     }
  151. };
  152.  
  153. int subtask, n, m;
  154. vector < int > ans[2];
  155. ll cost[2 * maxn + 10];
  156. Dinic D;
  157.  
  158. int main()
  159. {
  160.     ios_base::sync_with_stdio(0);
  161.     cin.tie(0);
  162.     cout.tie(0);
  163.     if (fopen("STADIUM.INP", "r"))
  164.     {
  165.         freopen("STADIUM.INP", "r", stdin);
  166.         freopen("STADIUM.OUT", "w", stdout);
  167.     }
  168.  
  169.     cin >> subtask;
  170.     cin >> n >> m;
  171.     D = Dinic(n + m + 2);
  172.     for (int i = 1; i <= n; i++)
  173.     {
  174.         cin >> cost[i];
  175.         // cout << 0 << ' ' << i << ' ' << cost[i], el;
  176.         D.add_edge(0, i, cost[i]);
  177.     }
  178.     for (int i = 1; i <= m; i++)
  179.     {
  180.         cin >> cost[i + n];
  181.         // cout << i + n << ' ' << 1 + n + m << ' ' << cost[i + n], el;
  182.         D.add_edge(i + n, 1 + n + m, cost[i + n]);
  183.     }
  184.     for (int i = 1; i <= n; i++)
  185.         for (int j = 1; j <= m; j++)
  186.         {
  187.             char c;
  188.             cin >> c;
  189.             if (c == '1')
  190.             {
  191.                 // cout << i << ' ' << j + n << ' ' << 1000, el;
  192.                 // adj[i].push_back(j + n);
  193.                 // adj[j + n].push_back(i);
  194.                 D.add_edge(i, j + n, INF);
  195.             }
  196.         }
  197.     // el;
  198.     ll min_cost = D.maxflow(0, n + m + 1);
  199.     cout << min_cost, el;
  200.     for (auto x: D.get_min_cut_edges(0))
  201.     {
  202.         int u, v;
  203.         ll cap, f;
  204.         tie(u, v, cap, f) = x;
  205.         if (v <= n)
  206.             ans[0].push_back(v);
  207.         else
  208.             ans[1].push_back(u - n);
  209.     }
  210.     cout << ans[0].size() << ' ';
  211.     for (int x: ans[0])
  212.         cout << x << ' ';
  213.     el;
  214.     cout << ans[1].size() << ' ';
  215.     for (int x: ans[1])
  216.         cout << x << ' ';
  217. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0 
0
https://ideone.com/GfJGHW
language:
C++14 (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!