Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.6 kB
1
Indexable
Never
#include <ios>
#include <iostream>
#include <vector>

struct flow_type {
    int64_t left{ 0 };
    int64_t right{ 0 };
};

struct data_type {
    const int n;
    std::vector<int> left;
    std::vector<int> right;
    std::vector<std::vector<int>> graph;

    data_type(int n): n(n) {}
};

void dfs(int v, std::vector<bool>& visited, const data_type& data, flow_type& flow)  {
  if (v > data.n) {
     flow.right += data.right[v - data.n]; 
    } else { 
        flow.left += data.left[v];
    }

  visited[v] = true;

  for(size_t i = 0; i < data.graph[v].size(); ++i) {
    int to = data.graph[v][i];

    if (!visited[to]) {
         dfs(to, visited, data, flow);
    }
  }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, k;
    std::cin >> n;
    std::cin >> k;

    data_type data(n);
    data.left.resize(n + 1, 0);
    data.right.resize(n + 1, 0);
    data.graph.resize(2*n + 1, std::vector<int>());

    for (int i = 1; i <= n; ++i) {
        std::cin >> data.left[i];
    }

    for (int i = 1; i <= n; ++i) {
        std::cin >> data.right[i];
    }

    int from, to;
    for (int i = 0; i < k; ++i) {
        std::cin >> from;
        std::cin >> to;

        data.graph[from].push_back(to + n); 
        data.graph[to + n].push_back(from);
    }

    int64_t res = 0;
    std::vector<bool> visited(data.graph.size(), false);

    for(int i = 1; i <= n; i++) {
        if(!visited[i]) {
            flow_type flow;
            dfs(i, visited, data, flow);
            res += std::min(flow.left, flow.right);
        }
    }

    std::cout << res << "\nm";
    return 0;
}
Leave a Comment