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

Download