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;
}