MINCUT – SPOJ

Đề bài: http://vn.spoj.com/problems/MINCUT/

Thuật toán:

• Với mỗi cách cắt ngang, cắt dọc. Ta chặt nhị phân tìm nhát cắt sao cho độ chênh lệch 2 phần nhỏ nhất.
• Chú ý với mỗi cách cắt ta phải chặt nhị phân 2 lần: value >= trunggian và value <= trunggian
• Các bạn có thể đọc code để hiểu rõ hơn

Code:

uses    math;
const   fi='';
        fo='';
        maxn=trunc(1e3)+3;
        oo=trunc(1e15);
type    data=record
                x,y,u,v:longint;
                end;
var     m,n,i,j,k:longint;
        s:array[0..maxn,0..maxn] of int64;
        a:array[1..maxn,1..maxn] of longint;
        q:array[1..maxn*maxn] of data;
        res     :int64;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n,k);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    for i:=1 to k do
        with q[i] do
                read(x,y,u,v);
    close(input);
end;
procedure init;
begin
    for i:=1 to m do
        for j:=1 to n do s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];
end;
function tinh(x,y,u,v:longint):int64;
begin
        exit(s[u,v]+s[x-1,y-1]-s[x-1,v]-s[u,y-1]);
end;
procedure solve;
var     tam,tam2        :int64;
        d,c,g   :longint;
begin
assign(output,fo);rewrite(output);
    for i:=1 to k do
      with q[i] do
        begin
            tam:=tinh(x,y,u,v);
            tam2 := tam div 2;
            res := oo;
            // cat hang
            d :=x; c:=u-1;
            g := (d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,g,v)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=c downto d do
                if tinh(x,y,g,v)<=tam2 then
                        begin
                                res := min(res,tam-2*tinh(x,y,g,v));
                        end;
            d:=x; c:=u-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,g,v)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=d to c do
                if tinh(x,y,g,v)>=tam2 then
                        begin
                                res := min(res,2*tinh(x,y,g,v)-tam);
                        end;
            // cat cot;
            d:=y; c:=v-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,u,g)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=c downto d do
                if tinh(x,y,u,g)<=tam2 then
                        begin
                                res := min(res,tam-2*tinh(x,y,u,g));
                        end;
            d:=y; c:=v-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,u,g)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=d to c do
                if tinh(x,y,u,g)>=tam2 then
                        begin
                                res := min(res,2*tinh(x,y,u,g)-tam);
                        end;
            writeln(res);
        end;
end;
begin
    nhap;
    init;
    solve;
end.