LIGHT - Hệ thống đèn
Tác giả: khuc_tuan
Ngôn ngữ: Java
import java.io.*;
import java.util.*;
public class Main {
int n,m,k,st,en,sl;
int[] a,b,q,la,e;
int[][] c, f;
void nhap() throws Exception{
BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(kb.readLine());
m=Integer.parseInt(st.nextToken());
n=Integer.parseInt(st.nextToken());
k=Integer.parseInt(st.nextToken());
en=m+n+2;
a=new int[m+1];
b=new int[n+1];
c=new int[m+n+3][m+n+3];
f=new int[m+n+3][m+n+3];
q=new int[m+n+3];
la=new int[m+n+3];
e=new int[m+n+3];
st=new StringTokenizer(kb.readLine());
for(int i=1;i<=m;++i) a[i]=Integer.parseInt(st.nextToken());
st=new StringTokenizer(kb.readLine());
for(int i=1;i<=n;++i) b[i]=Integer.parseInt(st.nextToken());
int u,v;
for(int i=1;i<=k;++i){
st=new StringTokenizer(kb.readLine());
u=Integer.parseInt(st.nextToken());
v=Integer.parseInt(st.nextToken());
c[u][v+m]=100000000;
}
for(int i=1;i<=m;++i) c[en-1][i]=a[i];
for(int i=1;i<=n;++i) c[i+m][en]=b[i];
}
void tangluong(int v){
int u,dt=e[v];
sl+=dt;
while(v!=st){
u=la[v];
if(u<0){
u=-u;
f[v][u]-=dt;
v=u;
}
else{
f[u][v]+=dt;
v=u;
}
}
}
boolean bfs(){
int l,r,u,v;
q[l=r=0]=st;
Arrays.fill(la,0);
Arrays.fill(e,0);
e[st]=100000000;
la[st]=st;
while(l<=r){
u=q[l++];
for(v=1;v<=en;++v) if(e[v]==0){
if(c[u][v]>f[u][v]){
e[v]=Math.min(e[u],c[u][v]-f[u][v]);
la[v]=u;
q[++r]=v;
}
else if(f[v][u]>0) {
e[v]=Math.min(e[u],f[v][u]);
la[v]=-u;
q[++r]=v;
}
}
if(e[en]>0) {
tangluong(en);
return true;
}
}
return false;
}
void xuly(){
st=en-1;
while( bfs() ) ;
System.out.println(sl);
}
void run() throws Exception{
nhap();
xuly();
}
public static void main(String[] args) throws Exception {
new Main().run();
}
}