Задача А-Податковий інспектор 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];
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; }
