see https://github.com/yosupo06/library-checker-problems/issues/610

my AC does not pass this short test

In my case this test may help you

16 19
1 2
2 3
3 4
4 5
5 1
1 6
6 7
7 8
8 9
9 10
10 6
5 11
11 12
12 13
13 4
3 14
14 15
15 16
16 2

The sequence of contraction affects the solution if you do not repeat the process after release the blossom.

if you contract (6,7,8,9,10), (4,5,11,12,13), (2,3,14,15,16) first
   you get maximum matching.
but if you contract (1,2,3,4,5) first and don't repeat the process after release it
   you don't get to the maximum.

Hope this helps.

Hello all,

I've been studying this topic lately, and I came out with a question which answer I have not been able to find anywhere.

I know very well the history about Edmonds' Blossom algorithm, however, it is well known that a given matching is the maximum one if no more augmenting paths can be found on the graph. So, my question is the following one:

I implemented a simple DFS algorithm that tries to find an augmenting path, and if found, it makes the flip we all know and adds/removes the flipped edges to the matching. In my DFS I only mark nodes that are reached in even levels (i.e. nodes found after following a matched edge, plus the first unmatched node) as visited, furthermore I also care about the nodes in the active path so as to avoid stepping in the same node and generating cycles. So, why this does not work? of course the reason is because there are augmenting paths my algorithm cannot find, but why?

All of this converges to a simple question: why in Edmonds' algorithm is it necessary to shrink blossoms? I've read many papers where it is explained how to shrink blossoms and why an augmenting path in the reduced graph is still valid in the expanded one, but they never explain why this is actually necessary!

Thanks for your help.

#include <cstdio>
#include <string.h>

using namespace std;

struct dat_edge
{
    int last,aim;
}edge[500000];
int temp[300],len_edge,pl[300],next[300],n,m;

void edge_insert(int x,int y)
{
    len_edge++;
    edge[len_edge].aim=y;
    edge[len_edge].last=pl[x];
    pl[x]=len_edge;
}

bool dfs(int root,int ps)
{
    if (temp[root]==ps) return false;
    if (ps==-1) return true;
    temp[root]=ps;
    int p=pl[root];
    bool t;
    while (p!=-1)
    {
        int tmp=edge[p].aim;
        if (temp[tmp]==ps) { p=edge[p].last;continue; }
        if (next[tmp]==-1) t=dfs(tmp,-1); else t=dfs(next[tmp],ps);
        if (t)
        {
            next[root]=edge[p].aim;
            next[edge[p].aim]=root;
            return true;
        }
        p=edge[p].last;
    }
    return false;
}

int main()
{
    //freopen("1099.in","r",stdin);
    //freopen("1099.out","w",stdout);
    int i,j,k,ans,coun,x,y;
    bool ok;
    scanf("%d",&n);
    len_edge=-1;
    for (i = 0;i<=n;i++) pl[i]=-1;
    while (scanf("%d%d",&x,&y)!=EOF)
    {
        edge_insert(x,y);
        edge_insert(y,x);
    }
    coun=0;
    for (i = 0;i<=n;i++) next[i]=-1;
    memset(temp,0,sizeof(temp));
    ans=0;
    for (i = 1;i<=n;i++)
    {
        ok=false;
        if (next[i]==-1) ok=dfs(i,++coun);
        if (ok) ans++;
    }
    printf("%d\n",ans*2);
    for (i = 1;i<=n;i++)
    if (next[i]>i)
    {
        printf("%d %d\n",i,next[i]);
    }
}

Very intresting algo... and simple!

http://theory.cs.uni-bonn.de/blum/papers/gmatching.ps.Z

Did it use special Judge or somethine else?

does anybody have the test data of 12#,i am wrong on this test data for a long time,could someone help me?my thanks.

I can send it to anybody who has ACed his(or hers).

At first I got WA#12
I change a few codes then I got WA#1
I can not got WA#12
Who can help me?

20
9 13
12 14
12 19
12 20
13 18
13 20
17 20
18 20
//ans: 6

20
2 6
2 8
3 13
3 15
3 16
3 17
6 11
6 12
6 13
6 15
6 18
8 11
9 13
11 14
11 16
11 18
12 14
12 19
13 18
15 16
//ans: 14

10
1 4
1 6
1 8
4 10
4 3
3 7
4 6
6 2
2 5
5 9
//ans: 10

8
1 2
2 3
1 3
1 4
1 5
//ans: 4

4
1 2
1 3
1 4
2 3
//ans: 4

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
//ans: 10

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
//ans: 10

8
1 2
1 3
1 6
2 3
2 4
4 7
4 8
5 6
5 7
//ans: 8

8
1 2
1 7
1 8
2 5
2 6
3 4
3 7
4 5
5 6
//ans: 8

16
1 7
2 4
2 5
3 15
4 5
5 12
5 13
6 14
6 16
8 12
8 14
9 10
9 15
11 15
13 14
//ans: 14

5
1 2
2 3
3 4
3 5
1 5
//ans: 4

6
1 2
2 3
1 3
3 4
2 5
5 6
//ans: 6

5
1 2
2 3
1 3
3 4
2 5
//ans: 4

3
1 2
2 3
1 3
//ans: 3

10
1 2
2 3
3 5
2 4
9 10
//ans: 6

4
1 2
2 3
1 3
1 4
//ans: 4

5
1 2
1 3
1 4
1 5
//ans: 2

5
1 2
1 3
1 4
1 5
5 2
//ans: 4

program ural;
var n,a,b,z,i:byte;
    r:integer;
    h:array[1..222]of integer;
    l:array[1..49062]of integer;
    t:array[1..49062]of byte;
    p,u:array[1..222]of boolean;
    v:array[1..222]of byte;
procedure search(f,d:byte);
var r:integer;
  begin
    r:=h[d];
    p[d]:=true;
    while r<>0 do
      begin
        if(t[r]<>f)and(p[t[r]]=false)then
          begin
            if v[d]=0 then
              begin
                inc(z);
                v[d]:=t[r];
                v[t[r]]:=d;
              end;
            search(d,t[r]);
          end;
        r:=l[r];
      end;
  end;
function match(d:byte):boolean;
var r:integer;
  begin
    r:=h[d];
    p[d]:=false;
    while r<>0 do
      begin
        if(v[t[r]]>0)and(p[v[t[r]]])and(u[v[t[r]]]=false)and(match(v[t[r]]))then
          begin
            v[t[r]]:=d;
            v[d]:=t[r];
            exit(true);
          end;
        r:=l[r];
      end;
    u[d]:=true;
    exit(false);
  end;
begin
  readln(n);
  while not eof do
    begin
      readln(a,b);
      inc(r);
      l[r]:=h[a];
      h[a]:=r;
      t[r]:=b;
      inc(r);
      l[r]:=h[b];
      h[b]:=r;
      t[r]:=a;
    end;
  for i:=1 to n do
    if p[i]=false then
      search(0,i);
  for i:=1 to n do
    if v[i]=0 then
      begin
        fillchar(p,sizeof(p),true);
        if match(i) then
          inc(z);
      end;
  writeln(z*2);
  for i:=1 to n do
    if v[i]>i then
      writeln(i,' ',v[i]);
end.

New tests have been added. 91 authors have lost AC after rejudge. Thanks to Sergey Kopeliovich.

RT~~~

Who can tell me Test61?

New tricky tests have been added. 104 authors have lost AC after rejudge. Thanks to Arseny Smirnov.

Can you give me some another test data suite?
With correct output in each...
I feel, I do not understand this task properly(

Hi, I am making a project on Edmonds` flower tree algo, but I am having some difficulties on the actual implemention (I am currently in session so I can't really dedicate all my time to it). Can someone who has solved it in C/C++ please send me his code, or (preferred) send a very short step by step instruction how to implement the main steps - shrinking and expanding blossoms seems to worry me. Thanks very much in advance!
My email is slayer_ac[ a t ]abv[ d o t ]bg

Edited by author 29.06.2009 18:35

I wonder how many tests there are....

TL was decreased to 0.5 sec.
New tests were added. Thanks to Vsevolod Oparin.

35 authors have lost AC.