ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1099. Work Scheduling

I have created a especial test data which some bad "Flower Tree" algorithm can not pass easily. Would you like to test your programs with my test data?
Posted by xreborner 25 Apr 2003 14:29
Input:

10
1 2
1 9
1 10
2 5
2 6
3 4
3 9
3 10
4 7
4 8
5 6
5 8
7 8

Key:

5

1 - 10
2 - 6
3 - 9
4 - 7
5 - 8

Input:

10
10 9
10 2
10 1
9 6
9 5
8 7
8 2
8 1
7 4
7 3
6 5
6 3
4 3

Key:

5

1 - 8
2 - 10
3 - 6
4 - 7
5 - 9
I got trapped with your test #1. It seems my prog can't find an augumentable path after matching 4 pairs of vertices. Could you help me?
Posted by Maigo Akisame (maigoakisame@yahoo.com.cn) 28 Jun 2004 15:32
program ural1099;
const
  maxn=222;
var
  g:array[1..maxn,1..maxn]of shortint;
    {0:no path;1:path not in the augtree;-1:path in the augtree}
  l:array[1..maxn,1..2]of byte;
    {l[i,1]:the vertex before i on the augpath, if it's uncovered;
     l[i,2]:the vertex before i on the augpath, if it's covered}
  p:array[1..maxn]of byte;
    {0 if it's uncovered, otherwise <i,p[i]> is a matched edge}
  n,i,j,total:byte;
procedure exchange(i,j:integer);
  {exchange matched and unmatched edges on the augpath}
  begin
    p[j]:=i;
    while l[i,2]<>255 do begin
      p[i]:=j;j:=l[i,2];
      p[j]:=l[j,1];i:=p[j];
    end;
    p[i]:=j;
  end;
function aug:boolean;
  var
    i,j,k{root of blossom},q,v:byte;
    s:set of 1..maxn;{Vertices in the blossom}
    more:boolean;{Whether to go on searching for augpath}
  begin
    aug:=true;
    repeat
      more:=false;
      for i:=1 to n do
        if l[i,2]>0 then{i is an outer vertex}
          for j:=1 to n do
            if (g[i,j]>0) and (p[i]<>j) then{an unmatched edge exists}
              if (l[j,1]=0) and (l[j,2]=0) then{j isn't in the interlaced tree}
                if p[j]=0 then begin{j is uncovered}
                  exchange(i,j);
                  exit;
                end
                else begin{j is covered}
                  g[i,j]:=-g[i,j];g[j,i]:=-g[j,i];
                  l[j,1]:=i;l[p[j],2]:=j;
                  g[j,p[j]]:=-g[j,p[j]];g[p[j],j]:=-g[p[j],j];
                  more:=true;
                end
              else if (l[j,1]=0) and (l[j,2]>0) then begin
                {i and j are both outer vertices, build blossom}
                more:=true;
                g[i,j]:=-g[i,j];g[j,i]:=-g[j,i];
                s:=[i];k:=i;v:=2;
                while l[k,v]<>255 do begin
                  k:=l[k,v];s:=s+[k];v:=3-v;
                end;
                k:=j;v:=2;
                while not (k in s) do begin
                  k:=l[k,v];v:=3-v;
                end;
                if l[i,1]=0 then begin{one blossom for i is enough}
                  l[i,1]:=j;q:=i;v:=2;
                  while q<>k do begin
                    l[l[q,v],v]:=q;q:=l[q,v];v:=3-v;
                  end;
                end;
                l[j,1]:=i;q:=j;v:=2;
                while q<>k do begin
                  l[l[q,v],v]:=q;q:=l[q,v];v:=3-v;
                end;
              end;
    until not more;
    aug:=false;
  end;
procedure match;
  var
    i,j,k:byte;
    b:boolean;
  begin
    fillchar(p,sizeof(p),0);
    repeat
      i:=0;
      repeat
        inc(i);
        if p[i]=0 then begin
          fillchar(l,sizeof(l),0);
          l[i,2]:=255;
          b:=aug;
          for j:=1 to n do
            for k:=1 to n do
              g[j,k]:=abs(g[j,k]);
        end
        else
          b:=false;
      until (i>n) or b;
      if i<=n then inc(total);
    until (i>n) or (total=n div 2);
  end;
begin
  fillchar(g,sizeof(g),0);
  readln(n);
  while not eof(input) do begin
    readln(i,j);
    g[i,j]:=1;g[j,i]:=1;
  end;

  total:=0;
  match;

  writeln(total*2);
  for i:=1 to n do
    if p[i]>0 then begin
      writeln(i,' ',p[i]);
      p[p[i]]:=0;
    end;
end.