Задача А-Податковий інспектор
CONST Dim = 1007;
VAR A,B,B0,C,C0,D,D0:Array[0..Dim] of longint;
N,flag:longint;
VAR NT,tt,ii,jj:integer;
BEGIN
read(NT);
for tt:=1 to NT do
begin
read(N);
for jj:=1 to N do B0[jj] := 0;
for jj:=1 to N do B[jj] := 0;
for jj:=1 to N do D0[jj] := 0;
for jj:=1 to N do D[jj] := 0;
for jj:=1 to N do A[jj] := 0;
for jj:=1 to N do C[jj] := 0;
for ii:=1 to N do
begin
for jj:=1 to N do B0[jj] := B[jj];
for jj:=1 to N do B[jj] := 0;
for jj:=1 to N do D0[jj] := D[jj];
for jj:=1 to N do D[jj] := 0;
for jj:=1 to N do A[jj] := 0;
for jj:=1 to N do C[jj] := 0;
for jj:=1 to N do
begin
read(A[jj]);
B[jj] := B0[jj] + A[jj]; {cols sum}
C[jj] := C[jj-1] + A[jj]; {rows sum}
flag := 0;
if (B[jj] mod 2 = 0) AND (D[jj-1]=0)
then flag:=1
else if (C[jj] mod 2 = 0) AND (D0[jj]=0) then flag:=1;
D[jj]:=flag;
end;
end;
writeln(D[N]);
end;
END.
Задача B-Обласна олімпіада
#define N 103
#define INF 100000000
#define bool int
#define false 0
#define true 1
#include "memory.h";
#include "iostream.h"
int max(int a,int b)
{
if(a>b) return a; else return b;
}
int min(int a,int b)
{
if(a<b) return a; else return b;
}
int cost[N][N];
int n, max_match;
int lx[N], ly[N];
int xy[N];
int yx[N];
bool S[N], T[N];
int slack[N];
int slackx[N];
int prev[N];
void init_labels()
{
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
lx[x] = max(lx[x], cost[x][y]);
}
void update_labels()
{
int x, y, delta = INF;
for (y = 0; y < n; y++)
if (!T[y])
delta = min(delta, slack[y]);
for (x = 0; x < n; x++)
if (S[x]) lx[x] -= delta;
for (y = 0; y < n; y++)
if (T[y]) ly[y] += delta;
for (y = 0; y < n; y++)
if (!T[y])
slack[y] -= delta;
}
void add_to_tree(int x, int prevx)
{
S[x] = true;
prev[x] = prevx;
for (int y = 0; y < n; y++)
if (lx[x] + ly[y] - cost[x][y] < slack[y])
{
slack[y] = lx[x] + ly[y] - cost[x][y];
slackx[y] = x;
}
}
void augment()
{
if (max_match == n) return;
int x, y, root;
int q[N], wr = 0, rd = 0;
memset(S, false, sizeof(S));
memset(T, false, sizeof(T));
memset(prev, -1, sizeof(prev));
for (x = 0; x < n; x++)
if (xy[x] == -1)
{
q[wr++] = root = x;
prev[x] = -2;
S[x] = true;
break;
}
for (y = 0; y < n; y++)
{
slack[y] = lx[root] + ly[y] - cost[root][y];
slackx[y] = root;
}
while (true)
{
while (rd < wr)
{
x = q[rd++];
for (y = 0; y < n; y++)
if (cost[x][y] == lx[x] + ly[y] && !T[y])
{
if (yx[y] == -1) break;
T[y] = true;
q[wr++] = yx[y];
add_to_tree(yx[y], x);
}
if (y < n) break;
}
if (y < n) break;
update_labels();
wr = rd = 0;
for (y = 0; y < n; y++)
if (!T[y] && slack[y] == 0)
{
if (yx[y] == -1)
{
x = slackx[y];
break;
}
else
{
T[y] = true;
if (!S[yx[y]])
{
q[wr++] = yx[y];
add_to_tree(yx[y], slackx[y]);
}
}
}
if (y < n) break;
}
if (y < n)
{
max_match++;
for (int cx = x, cy = y, ty; cx != -2; cx = prev[cx], cy = ty)
{
ty = xy[cx];
yx[cy] = cx;
xy[cx] = cy;
}
augment();
}
}
int hungarian()
{
int ret = 0;
max_match = 0;
memset(xy, -1, sizeof(xy));
memset(yx, -1, sizeof(yx));
init_labels();
augment();
for (int x = 0; x < n; x++)
ret += cost[x][xy[x]];
return ret;
}
int main()
{
int ii,jj;
cin>>n;
for(ii=0;ii<n;ii++)
for(jj=0;jj<n;jj++) cin>>cost[ii][jj];
hungarian();
int sum = 0;
for(int iii=0;iii<n;iii++) sum+=cost[iii][xy[iii]];
cout<<sum<<endl;
return 0;
}