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 1076. Trash

Can somebody send me a good algo of min cost max matching? I've found only O(N^4)
Posted by vladu adrian 8 Jul 2003 02:02
Can somebody send me a good algo of min cost max matching?
I've found a solution, but it runs in O(n^4), so I get time limit
exceeded for some tests.
Just use Hungarian algo (-)
Posted by Dmitry 'Diman_YES' Kovalioff 8 Jul 2003 13:29
Re: Just use Hungarian algo (-)
Posted by vladu adrian 11 Jul 2003 01:17
> I've used a Hungarian algo that I've found on the NET. I don't know
if it's correct because, for some tests it cycles to the infinite
because no modifications can be done. Please, could somebody give me
an algo that works?
Here's my source. Usually it works fine but, as I said, in some cases
it doesn't work.
program trash;
const nmax = 150;
var a, d : array [1..nmax, 1..nmax] of integer;

    s : array [1..nmax] of integer;
    nz : array [1..nmax] of byte;

    m, b : array [1..nmax, 1..nmax] of boolean;
    hasm, found : boolean;

    mlin, mcol : array [1..nmax] of boolean;

    ming1 : integer;
    sum : longint;

    N, i, j : byte;



procedure readdata;
begin
{  assign(input, 'trash.in'); reset(input);}
  fillchar(s, sizeof(s), 0);
  readln(N);
  for i:=1 to N do
  begin
    for j:=1 to N do
    begin
      read(d[i,j]);
      inc(s[i], d[i,j]);
    end;
    for j:=1 to N do
    begin
      a[i,j]:=s[i]-d[i,j];
      d[i,j]:=a[i,j];
    end;
    readln;
  end;
{  close(input);}
end;

procedure DoZero;
var i, j : byte;
    min : integer;
begin
  for i:=1 to N do
  begin
    min:=a[i,1];
    for j:=2 to N do
      if a[i,j]<min then
        min:=a[i,j];
    for j:=1 to N do
      dec(a[i,j], min);
  end;
  for j:=1 to N do
  begin
    min:=a[1,j];
    for i:=2 to N do
      if a[i,j]<min then
        min:=a[i,j];
    for i:=1 to N do
      dec(a[i,j],min);
  end;
end;

function DoMark:boolean;
var i, j, k, min, r : byte;
begin
  fillchar(nz, sizeof(nz), 0);
  fillchar(m, sizeof(m), 0);
  fillchar(b, sizeof(b), 0);
  for i:=1 to N do
    for j:=1 to N do
      if a[i,j]=0 then
        inc(nz[i]);
  for k:=1 to N do
  begin {choose a row with min 0's}
    min:=255;
    for i:=1 to N do
      if (nz[i]>0)and(nz[i]<min) then
      begin
        min:=nz[i];
        r:=i;
      end;
    if min=255 then
    begin
      DoMark:=false;
      exit;
    end;
    j:=1;
    nz[r]:=0;
    while (a[r,j]<>0)or(b[r,j]) do inc(j);
    m[r,j]:=true; {is marked}
    for i:=j+1 to N do
      if (a[r,i]=0) then
        b[r,i]:=true;
    for i:=1 to N do
      if (i<>r)and(a[i,j]=0) then
      begin
        b[i,j]:=true;
        dec(nz[i]);
      end;
  end;
  DoMark:=true;
end;

begin
  readdata;
  DoZero;


  while not DoMark do
  begin

    fillchar(mlin, sizeof(mlin), false);
    fillchar(mcol, sizeof(mcol), false);

    for i:=1 to N do
    begin
      hasm:=false;
      for j:=1 to N do
        if m[i,j] then
        begin
          hasm:=true;
          break;
        end;
      if not hasm then mlin[i]:=true;
    end;


    repeat
      found:=false;
      for i:=1 to N do
        if mlin[i] then
          for j:=1 to N do
            if (b[i,j])and(mcol[j]=false) then
            begin
              mcol[j]:=true;
              found:=true;
            end;

      if found then
        for j:=1 to N do
          if mcol[j] then
            for i:=1 to N do
              if (m[i,j])and(not mlin[i]) then
              begin
                mlin[i]:=true;
                found:=true;
              end;
    until not found;
    {i've made the marking}

    ming1:=maxint;
    for i:=1 to N do
      for j:=1 to N do
        if (mlin[i])and(not mcol[j])and(a[i,j]<ming1) then
          ming1:=a[i,j];

    for i:=1 to N do
      for j:=1 to N do
        if (mlin[i])and(not mcol[j]) then
          dec(a[i,j], ming1);

    for i:=1 to N do
      for j:=1 to N do
        if (not mlin[i])and(mcol[j]) then
          inc(a[i,j], ming1);
  end;

  sum:=0;
  for i:=1 to N do
    for j:=1 to N do
      if m[i,j] then
        inc(sum, d[i,j]);
  writeln(sum);
end.
Re: Can somebody send me a good algo of min cost max matching? I've found only O(N^4)
Posted by partisan (Andrey Korotkov) 6 Dec 2007 19:25
no text

Edited by author 12.12.2007 00:40
Re: Can somebody send me a good algo of min cost max matching? I've found only O(N^4)
Posted by Lomir 6 Dec 2007 20:14
Usual mincost maxflow got easily AC here.
I used maxflow with dijkstra to path searching.
Dijkstra works O(n^2) ant increases flow by 1 eachtime.
So we need only O(n) dijkstras to reach maxflow.
Whole complexivity is O(n^3). In c++ is works for 0.171sec.
Re: Just use Hungarian algo (-)
Posted by partisan (Andrey Korotkov) 12 Dec 2007 00:42
But how? Its complexity is O(n^4). I got TLE. Please, someone, tell me how to do it.
Re: Can somebody send me a good algo of min cost max matching? I've found only O(N^4)
Posted by Liu Strong 14 Apr 2008 20:35
How can you use Dijkstra since there are some edges which have minus values(values <0)?
I used Bellman-Ford algo, and it doesn't run out of time.
Re: Can somebody send me a good algo of min cost max matching? I've found only O(N^4)
Posted by Chmel_Tolstiy 16 Apr 2008 12:39
Use Dejkstra with potenciales. Modify weigth of eadges ... It's standart algorithm.
No subject
Posted by ACcreator 17 Aug 2009 16:01
I use SPFA but my problem got TLE with TEST#4
10 years later...
Posted by Chitanda Eru 28 Sep 2013 18:25
Testing machine is so fast now that an O(N^4) algo gets AC in less than 0.5s.
Re: 10 years later...
Posted by die_young 14 Aug 2018 18:17
Hungarian: 15ms
Min cost flow with Dijkstra: 171 ms
Min cost flow with optimized Bellman-Ford: 109 ms
¯\_(ツ)_/¯