Субота, 23.09.2017, 07:32
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Меню сайту
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Форма входу
 Авторські розв'язки
Задача А-Податковий інспектор
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;
}
Copyright MyCorp © 2017
Пошук
Календар
«  Вересень 2017  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
252627282930
Архів записів
Друзі сайту
Обдаровані діти

Step by Step - Школа олімпійського резерву

Відділ інформаційних технологій та дистанційного навчання ХОІППО