fork download 
  1. // J
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. //#define int long long
  7. #define bint __int128
  8. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  9.  
  10. const int oo = 1e9;
  11.  
  12. struct edge{
  13.     int u, v, cap, flow;
  14. };
  15.  
  16. struct Dinic{
  17.     int n;
  18.     vector<int> dist, par, idEdge, curId;
  19.     vector<vector<int>> adj;
  20.     vector<edge> edges;
  21.  
  22.     Dinic(int nn){
  23.         n = nn;
  24.         dist.resize(n + 1);
  25.         adj.resize(n + 1);
  26.         par.resize(n + 1);
  27.         idEdge.resize(n + 1);
  28.         curId.resize(n + 1);
  29.     }
  30.  
  31.     void addEdge(int u, int v, int c){
  32.         adj[u].push_back(edges.size());
  33.         edges.push_back({u, v, c, 0});
  34.         adj[v].push_back(edges.size());
  35.         edges.push_back({v, u, c, 0});
  36.     }
  37.  
  38.     int flow(int src, int sink) {
  39.         int totalFlow = 0;
  40.         while(isPath(src, sink)){
  41.             for(int i = 1; i <= n; i++)
  42.                 curId[i] = 0;
  43.             while(int newFlow = dfs(src, oo, sink))
  44.                 totalFlow += newFlow;
  45.         }
  46.  
  47.         return totalFlow;
  48.     }
  49.  
  50.     bool isPath(int src, int sink){
  51.         for(int i = 1; i <= n; i++)
  52.             dist[i] = oo;
  53.  
  54.         queue<int> q;
  55.         q.push(src);
  56.         dist[src] = 0;
  57.  
  58.         while(!q.empty()){
  59.             int u = q.front();
  60.             q.pop();
  61.             if(u == sink)
  62.                 break;
  63.  
  64.             for(auto idx : adj[u]){
  65.                 auto [_,v,c, f] = edges[idx];
  66.                 if(f < c && dist[v] == oo){
  67.                     dist[v] = dist[u] + 1;
  68.                     par[v] = u;
  69.                     idEdge[v] = idx;
  70.                     q.push(v);
  71.                 }
  72.             }
  73.         }
  74.         return dist[sink] < oo;
  75.     }
  76.  
  77.     int dfs(int u, int flow, int sink){
  78.         if(!flow)
  79.             return 0;
  80.  
  81.         if(u == sink)
  82.             return flow;
  83.  
  84.         for(;curId[u] < adj[u].size(); curId[u]++){
  85.             int idx = adj[u][curId[u]];
  86.             auto [_, v, c, f] = edges[idx];
  87.  
  88.             if(dist[v] != dist[u] + 1)
  89.                 continue;
  90.  
  91.             int newFlow = dfs(v, min(flow, c - f), sink);
  92.             if(newFlow){
  93.                 edges[idx].flow += newFlow;
  94.                 edges[idx ^ 1].flow -= newFlow;
  95.                 return newFlow;
  96.             }
  97.         }
  98.         return 0;
  99.     }
  100.  
  101. };
  102.  
  103. int n, m, k, c;
  104.  
  105. int id(int i, int j){
  106.     return (i - 1) * (m + 1) + j;
  107. }
  108.  
  109. void getShitDone() {
  110.     cin >> n >> m>> k >> c;
  111.  
  112.     Dinic dinic(n * (m + 1) + 6);
  113.     int src = n * (m + 1) + 4, sink = n * (m + 1) + 5, shift = 1e6;
  114.     int p[n + 1][ m + 1];
  115.     for(int i = 1; i <= n; i++){
  116.         dinic.addEdge(src, id(i, 1), oo);
  117.         for(int j = 1; j <= m; j++){
  118.             cin >> p[i][j];
  119.             dinic.addEdge(id(i, j), id(i, j + 1), shift - p[i][j]);
  120. //            dinic.addEdge(id(i, j + 1), id(i, j), shift - p[i][j]);
  121.         }
  122.         dinic.addEdge(id(i, m + 1), sink, oo);
  123.     }
  124.  
  125.     for(int i = 0; i < k; i++){
  126.         int a, b; cin >> a >> b;
  127.         for(int j = 2; j <= m; j++) {
  128.             dinic.addEdge(id(a, j), id(b, j), c);
  129. //            dinic.addEdge(id(b, j), id(a, j), c);
  130.         }
  131.     }
  132.  
  133.     cout << n * shift - dinic.flow(src, sink);
  134. }
  135.  
  136. signed main() {
  137.     _3bkarm
  138.  
  139.     int ts = 1;
  140. //    cin >> ts;
  141.     while (ts--) getShitDone();
  142.  
  143.     return 0;
  144. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/jwuPkJ
language:
C++ (gcc 8.3)
created:
3 days 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!