uoj#78. 二分图最大匹配

从前一个和谐的班级，有 nlnl 个是男生，有 nrnr 个是女生。编号分别为 1,…,nl1,…,nl 和 1,…,nr1,…,nr。

有若干个这样的条件：第 vv 个男生和第 uu 个女生愿意结为配偶。

请问这个班级里最多产生多少对配偶？

输入格式

第一行三个正整数，nl,nr,mnl,nr,m。

接下来 mm 行，每行两个整数 v,uv,u 表示第 vv 个男生和第 uu 个女生愿意结为配偶。保证 1≤v≤nl1≤v≤nl，1≤u≤nr1≤u≤nr，保证同一个条件不会出现两次。

输出格式

第一行一个整数，表示最多产生多少对配偶。

接下来一行 nlnl 个整数，描述一组最优方案。第 vv 个整数表示 vv 号男生的配偶的编号。如果 vv 号男生没配偶请输出 00。

样例一

input

output

2

2 1

explanation

11 号男生跟 22 号女生幸福地生活在了一起～

22 号男生跟 11 号女生幸福地生活在了一起～

样例二

input

output

1

1 0

explanation

班上一个女神一个女汉子，两个男生都去追女神。一种最优方案是：

11 号男生跟 11 号女生幸福地生活在了一起～

22 号男生孤独终生。= =||

限制与约定

1≤nl,nr≤5001≤nl,nr≤500，1≤m≤2500001≤m≤250000。

时间限制：1s

空间限制：256MB

打个板子玩玩，不料还WA了一次。原因是把队列数组也开成-550~550了。

 program rrr(input,output);

 const

   inf=;

 type

   etype=record

      t,c,next,rev:longint;

   end;

 var

   e:array[..]of etype;

   a,cur,d:array[-..]of longint;

   q:array[..]of longint;

   l,r,i,x,y,j,m,cnt,ans,h,t:longint;

 function min(a,b:longint):longint;

 begin

    if a<b then exit(a) else exit(b);

 end;

 procedure ins(x,y,c:longint);

 begin

    inc(cnt);e[cnt].t:=y;e[cnt].c:=c;e[cnt].next:=a[x];a[x]:=cnt;

 end;

 procedure add(x,y,c:longint);

 begin

    ins(x,y,c);e[cnt].rev:=cnt+;ins(y,x,);e[cnt].rev:=cnt-;

 end;

 procedure bfs;

 begin

    for i:=-l to r+ do d[i]:=-;d[]:=;

    h:=;t:=;q[]:=;

    while h<t do

       begin

          inc(h);

          i:=a[q[h]];

          while i<> do

             begin

                if (d[e[i].t]=-) and (e[i].c>) then

                   begin

                      d[e[i].t]:=d[q[h]]+;

                      inc(t);q[t]:=e[i].t;

                   end;

                i:=e[i].next;

             end;

       end;

 end;

 function dfs(k,f:longint):longint;

 var

   ans,t,i:longint;

 begin

    if (k=r+) or (f=) then exit(f);

    ans:=;i:=cur[k];

    while i<> do

       begin

          if (d[e[i].t]=d[k]+) and (e[i].c>) then

             begin

                t:=dfs(e[i].t,min(f,e[i].c));

                dec(e[i].c,t);inc(e[e[i].rev].c,t);

                inc(ans,t);dec(f,t);

                if f= then break;

             end;

          i:=e[i].next;cur[k]:=i;

       end;

    if f> then d[k]:=-;

    exit(ans);

 end;

 begin

    assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output);

    readln(l,r,m);

    fillchar(a,sizeof(a),);cnt:=;

    for i:= to l do add(,-i,);

    for i:= to m do begin readln(x,y);add(-x,y,); end;

    for i:= to r do add(i,r+,);

    ans:=;

    while true do

       begin

          bfs;

          if d[r+]=- then break;

          for i:=-l to r+ do cur[i]:=a[i];

          ans:=ans+dfs(,inf);

       end;

    writeln(ans);

    for i:= to l do

       begin

          j:=a[-i];

          while j<> do begin if e[j].c= then break;j:=e[j].next; end;

          if j= then write(,' ') else write(e[j].t,' ');

       end;

    close(input);close(output);

 end.

巴特西

二分图最大匹配模板（pascal）

uoj#78. 二分图最大匹配

输入格式

输出格式

样例一

input

output

explanation

样例二

input

output

explanation

限制与约定

最新文章

热门文章