LIGHT - Hệ thống đèn
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <conio.h>
#define maxc 1111111111
#define maxn 311
using namespace std;
int n,m,k,s,t,c[maxn][maxn],f[maxn][maxn],qu[maxn],tr[maxn];
bool coduongtang(){
int dau,cuoi,u,v;
memset(tr,0,sizeof(tr));
dau = 1; cuoi = 1;
qu[dau] = s;
tr[s] = n+m+3;
// printf("co\n");
do{
u = qu[dau]; dau++;
for(v = 1;v<=n+m+2;v++){
if(tr[v]==0 && c[u][v]>f[u][v]){
tr[v] = u;
if(v==t)
return true;
cuoi++; qu[cuoi] = v;
}
}
}while(dau<=cuoi);
return false;
}
void duongtang(){
int delta,u,v;
delta = maxc;
v = t;
do{
u = tr[v];
if(c[u][v]-f[u][v]<delta) delta = c[u][v]-f[u][v];
v = u;
}while(v!=s);
v = t;
do{
u = tr[v];
f[u][v] = f[u][v]+delta;
f[v][u] = f[v][u]-delta;
v = u;
}while(v!=s);
}
int main(){
//freopen("LIGHT.in","r",stdin);
int i,u,v;
scanf("%d %d %d",&m,&n,&k);
memset(c,0,sizeof(c));
for(int i = 1;i<=m;i++) scanf("%d",&c[1][i+1]);
for(int i = 1;i<=n;i++) scanf("%d",&c[m+i+1][n+m+2]);
for(int i = 1;i<=k;i++){
scanf("%d %d",&u,&v);
c[u+1][m+v+1] = maxc;
}
s = 1;
t = n+m+2;
memset(f,0,sizeof(f));
do{
if(coduongtang()) duongtang();
else break;
}while(true);
int w = 0;
for(u = 1;u<=n+m+2;u++){
if(f[s][u]>0)
w+=f[s][u];
}
printf("%d",w);
//getch();
}