Source Code
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[]{ -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[]{ 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
#else
#endif
}

struct MCMF {
	struct edge {
		int from, to, cost, cap, flow, backEdge;
		edge() {
			from = to = cost = cap = flow = backEdge = 0;
		}
		edge(int from, int to, int cost, int cap, int flow, int backEdge) :
			from(from), to(to), cost(cost), cap(cap), flow(flow), backEdge(
				backEdge) {
		}
		bool operator <(const edge& other) const {
			return cost < other.cost;
		}
	};
	int n, src, dest;
	vector<vector<edge>> adj;
	MCMF(int n, int src, int dest) :
		n(n), src(src), dest(dest), adj(n) {
	}
	void addEdge(int u, int v, int cost, int cap) {
		edge e1 = edge(u, v, cost, cap, 0, adj[v].size());
		edge e2 = edge(v, u, -cost, 0, 0, adj[u].size());
		adj[u].push_back(e1);
		adj[v].push_back(e2);
	}
	pair<int, ll> minCostMaxFlow() {
		int maxFlow = 0;
		ll cost = 0;
		while (true) {
			vector<pair<int, int>> path = spfa();
			if (path.empty())
				break;
			int new_flow = INF;
			for (auto& it : path) {
				edge& e = adj[it.first][it.second];
				new_flow = min(new_flow, e.cap - e.flow);
			}
			for (auto& it : path) {
				edge& e = adj[it.first][it.second];
				e.flow += new_flow;
				cost += 1LL * new_flow * e.cost;
				adj[e.to][e.backEdge].flow -= new_flow;
			}
			maxFlow += new_flow;
		}
		return { maxFlow,cost };
	}
	enum visit {
		finished, in_queue, not_visited
	};
	vector<pair<int, int>> spfa() {
		vector<ll> dis(n, INF);
		vector<int> prev(n, -1), from_edge(n), state(n,
			not_visited);
		deque<int> q;
		dis[src] = 0;
		q.push_back(src);
		while (!q.empty()) {
			int u = q.front();
			q.pop_front();
			state[u] = finished;
			for (int i = 0; i < adj[u].size(); i++) {
				edge e = adj[u][i];
				if (e.flow >= e.cap || dis[e.to] <= dis[u] + e.cost)
					continue;
				dis[e.to] = dis[u] + e.cost;
				prev[e.to] = u;
				from_edge[e.to] = i;
				if (state[e.to] == in_queue)
					continue;
				if (state[e.to] == finished
					|| (!q.empty() && dis[q.front()] > dis[e.to]))
					q.push_front(e.to);
				else
					q.push_back(e.to);
				state[e.to] = in_queue;
			}
		}
		if (dis[dest] == INF)
			return {};
		vector<pair<int, int>> path;
		int cur = dest;
		while (cur != src) {
			path.push_back({ prev[cur], from_edge[cur] });
			cur = prev[cur];
		}
		reverse(path.begin(), path.end());
		return path;
	}
};


int main() {
	run();
	int n, m, k;
	cin >> n >> m >> k;
	int src = 0, dest = n + m + 1;
	MCMF flow(dest + 1, src, dest);
	vector<int> v(n + 1), v2(m + 1);
	for (int i = 1; i <= n; i++) {
		int match;
		cin >> match >> v[i];
		flow.addEdge(src, i, 0, match);
	}
	for (int i = 1; i <= m; i++) {
		int match;
		cin >> match >> v2[i];
		flow.addEdge(n + i, dest, 0, match);
	}
	while (k--) {
		int x, y;
		cin >> x >> y;
		flow.addEdge(x, y + n, v[x] + v2[y], INF);
	}
	pair<int, ll> p = flow.minCostMaxFlow();
	cout << p.first << ' ' << p.second << endl;
}
Copy
Even Flow AhmedEzzatG
GNU G++17
8098 ms
2.7 MB
Time Limit Exceeded