Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <set>
- using namespace std;
- const int X = 1e5 + 20;
- const int Inf = 1e9 + 7;
- int p;
- struct Edge {
- Edge() = default;
- Edge(int x, int c, int cap, int ind) : to(x), cost(c), capacity(cap), reverse(ind), flow(0) {};
- int to;
- int cost;
- int capacity;
- int reverse;
- int flow;
- };
- vector<Edge> edges;
- vector<int> g[X];
- vector<int> dists(X, Inf);
- vector<int> P(X, 0);
- int delta(Edge k) {
- return k.capacity - k.flow;
- }
- void add(int v, int u, int c = 0, int cap = 1) {
- Edge x(u, c, cap, edges.size() + 1);
- Edge y(v, -c, 0, edges.size());
- g[v].push_back(edges.size());
- g[u].push_back(edges.size() + 1);
- edges.push_back(x);
- edges.push_back(y);
- }
- bool dj(int s, int t) {
- dists.assign(X, Inf);
- set<pair<int, int>> d;
- d.insert({0, s});
- dists[s] = 0;
- while (!d.empty()) {
- auto x = *d.begin();
- int v = x.second;
- for (auto to: g[v]) {
- auto &e = edges[to];
- if (delta(e)) {
- int x = dists[v] + e.cost + P[v] - P[e.to];
- if (dists[e.to] > x) {
- d.erase({dists[e.to], e.to});
- dists[e.to] = x;
- d.insert({x, e.to});
- }
- }
- }
- d.erase(d.begin());
- }
- for (int i = 0; i < X; i++) {
- if (dists[i] != Inf) {
- P[i] += dists[i];
- }
- }
- return dists[t] < Inf;
- }
- int dfsW(int v, int t, vector<bool> &used, int fl = Inf) {
- if (v == t) {
- return fl == Inf ? 0 : fl;
- }
- used[v] = true;
- for (auto to: g[v]) {
- auto &e = edges[to];
- if (!used[e.to] && delta(e) && e.cost + P[v] - P[e.to] == 0) {
- int x = dfsW(e.to, t, used, min(fl, delta(e)));
- if (x) {
- e.flow += x;
- edges[e.reverse].flow -= x;
- return x;
- }
- }
- }
- return 0;
- }
- pair<int, int> MCMF(int s, int t) {
- vector<bool> used(X, false);
- int ans = 0;
- while (dj(s, t)) {
- dfsW(s, t, used);
- used.assign(X, false);
- }
- for (int i = 0; i < X; i++) {
- for (auto to: g[i]) {
- auto &e = edges[to];
- ans += e.flow * e.cost;
- }
- }
- int flow = 0;
- for (auto x : g[s]) {
- auto k = edges[x];
- flow += k.flow;
- }
- return {flow, ans / 2};
- }
- int main() {
- int n, m, k;
- cin >> n >> m >> k;
- cin >> p;
- int e1, e2;
- cin >> e1 >> e2;
- int size = n + 2 * m + k + 3;
- int Boots = 0;
- int PantsIn = n;
- int PantsOut = n + m;
- int Tunics = n + 2*m;
- vector<int> boots(n + 1);
- for (int i = 1; i <= n; ++i) {
- cin >> boots[i];
- add(0, i, boots[i]);
- }
- vector<int> pants(m + 1);
- for (int i = 1; i <= m; ++i) { // раздваиваем вершины
- cin >> pants[i];
- add(PantsIn + i, PantsOut + i);
- }
- vector<int> tunics(k + 1);
- for (int i = 1; i <= k; ++i) {
- cin >> tunics[i];
- add(Tunics + i, size - 2);
- }
- int a, b;
- for (int i = 0; i < e1; ++i) {
- cin >> a >> b;
- add(PantsOut + a, Tunics + b, tunics[b]);
- }
- for (int i = 0; i < e2; ++i) {
- cin >> a >> b;
- add(Boots + b, PantsIn + a, pants[a]);
- }
- add(size - 2, size - 1, 0, p);
- auto result = MCMF(0, size - 1);
- if (result.first < p) {
- cout << -1 << endl;
- return 0;
- }
- cout << result.second << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement