LIGHT - Hệ thống đèn

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<bits/stdc++.h>
using namespace std;

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int INF = 1e9;
vector<vector<pair<int, int> > > g;
vector<int> flow, c;
vector<pair<int, int> > trace;
int m, n, p;

template<class T> int size(const T &a) { return a.size(); }

void addEdge(int u, int v, int lim) {
	g[u].push_back(make_pair(v, size(c)));
	g[v].push_back(make_pair(u, size(c)+1));
	c.push_back(lim); c.push_back(0);
	flow.push_back(0); flow.push_back(0);
}

void enter() {
	cin >> m >> n >> p;
	g.resize(m+n+2); trace.resize(m+n+2);
	for(int i = 0; i < m; ++i) {
		int c; cin >> c;
		addEdge(0, i+1, c);
	}
	for(int i = 0; i < n; ++i) {
		int c; cin >> c;
		addEdge(m+i+1, m+n+1, c);
	}
	for(int i = 0; i < p; ++i) {
		int x, y; cin >> x >> y; --x; --y;
		addEdge(x+1, m+y+1, INF);
	}
}

int maxflow(int s, int t) {
	int res = 0;
	while(true) {
		fill(trace.begin(), trace.end(), make_pair(INF, INF));
		trace[s] = make_pair(-1, -1);
		queue<int> q; q.push(s);
		while(!q.empty()) {
			int u = q.front(); q.pop();
			if(u == t) break;
			TR(g[u], it) {
				int v = it->first, e = it->second;
				if(trace[v].first == INF && c[e] - flow[e] > 0)
					trace[v] = make_pair(u, e), q.push(v);
			}
		}
		if(trace[t].first == INF) break;
		int delta = INF;
		for(int v = t, u = trace[v].first; u != -1; v = u, u = trace[u].first)
			delta = min(delta, c[trace[v].second] - flow[trace[v].second]);
		for(int v = t, u = trace[v].first; u != -1; v = u, u = trace[u].first) {
			int e = trace[v].second;
			flow[e] += delta;
			flow[e ^ 1] -= delta;
		}
		res += delta;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	enter();
	cout << maxflow(0, m+n+1) << '\n';
	return 0;
}

Download