LIGHT - Hệ thống đèn
Tác giả: ll931110
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#define INF 1000000000
typedef long long ll;
using namespace std;
int f[210][210],c[210][210];
int trace[210];
int n,m,k;
int cnt = 0;
int start,end;
vector<int> adj[210];
bool findPath()
{
// cout << "begin findpath" << endl;
memset(trace,0,sizeof(trace));
queue<int> q; q.push(start); trace[start] = -1;
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i];
if (!trace[v] && c[u][v] > f[u][v])
{
trace[v] = u;
if (v == end) return true;
q.push(v);
};
};
};
return false;
};
void IncFlow()
{
int delta = INF,v = end;
while (v != start)
{
int u = trace[v];
delta = min(delta,c[u][v] - f[u][v]);
v = u;
};
v = end;
while (v != start)
{
int u = trace[v];
f[u][v] += delta; f[v][u] -= delta;
v = u;
};
};
void add_edge(int u,int v,int cost)
{
adj[u].push_back(v);
adj[v].push_back(u);
c[u][v] = cost;
};
void maxFlow()
{
while (1)
{
if (!findPath()) break;
IncFlow();
};
};
int main()
{
// freopen("light.in","r",stdin);
// freopen("light.ou","w",stdout);
scanf("%d %d %d", &m, &n, &k);
start = 1; end = n + m + 2;
memset(c,0,sizeof(c));
for (int i = 1; i <= m; i++)
{
int x; scanf("%d", &x);
add_edge(start,1 + i,x);
};
for (int i = 1; i <= n; i++)
{
int x; scanf("%d", &x);
add_edge(m + i + 1,end,x);
};
for (int i = 0; i < k; i++)
{
int x,y;
scanf("%d %d", &x, &y);
add_edge(1 + x,m + 1 + y,INF);
};
/* for (int i = 1; i <= end; i++)
{
for (int j = 0; j < adj[i].size(); j++) cout << adj[i][j] << ' ';
cout << endl;
};*/
memset(f,0,sizeof(f));
maxFlow();
int ret = 0;
for (int i = 0; i < adj[start].size(); i++)
{
int v = adj[start][i];
ret += f[start][v];
};
printf("%d\n", ret);
};