Poj1325 Machine Schedule & Poj2226 Muddy Fields — 二分图最小覆盖/最大匹配

Note: 本文最初于 2011年 在 hi.baidu.com/lydrainbowcat 发表。

POJ1325 Machine Schedule

• 有两台机器A,B及N个任务。每台机器有M种不同的模式。M,N <= 100。
• 对每个任务i给定a[i]和b[i]，表示如果该任务在A上执行，需要设置模式为a[i]，如果在B上执行，需要模式为b[i]。
• 任务可以以任意顺序被执行。但每台机器转换一次模式就要重启一次。要求合理分配任务并合理安排顺序，使得机器重启次数最少。

解法：

• 左部图是机器A上的模式，右部图是机器B上的模式，对于每个任务在a[i]和b[i]之间连边。
• 答案就是最小覆盖。

POJ2226 Muddy Fields

• 在一块N*M的矩形地面上，有一些格子是泥泞的，现在要用一些宽为1的木板把泥地盖住，并且不能盖住好地。木板可以重叠。问最少需要多少木板？ N,M<=50。

解法：

• 不能盖住好地，那么宽为1的木板只能放在行、列连通块里。
• 所以行、列连通块对应左、右部中的点，泥地对应边。
• 求二分图最小覆盖就是答案。

Source Code

Problem: 1325		User: lydliyudong
Memory: 1876K		Time: 0MS
Language: Pascal		Result: Accepted

• Source Code

var
 a:array[0..500,0..500]of longint;
 link:array[0..500]of longint;
 v:array[0..500]of boolean;
 ans,i,n,ma,mb,ai,bi,num:longint;

function dfs(p:longint):boolean;
 var
  i:longint;
 begin
  for i:=1 to a[p,0] do
   if not v[a[p,i]] then
    begin
     v[a[p,i]]:=true;
     if (link[a[p,i]]=0)or(dfs(link[a[p,i]])) then
      begin
       link[a[p,i]]:=p;
       exit(true);
      end;
    end;
  exit(false);
 end;

begin
 repeat
  read(ma);
  if seekeof then exit;
  ans:=0;
  readln(mb,n);
  fillchar(link,sizeof(link),0);
  fillchar(a,sizeof(a),0);
  for i:=1 to n do
   begin
    readln(num,ai,bi);
    if (ai=0)or(bi=0) then continue;
    inc(bi,ma);
    inc(a[ai,0]);
    a[ai,a[ai,0]]:=bi;
    inc(a[bi,0]);
    a[bi,a[bi,0]]:=ai;
   end;
  for i:=1 to ma-1 do
   begin
    fillchar(v,sizeof(v),0);
    if dfs(i) then inc(ans);
   end;
  writeln(ans);
 until ans=maxlongint;
end.

Source Code

Problem: 2226		User: lydliyudong
Memory: 4684K		Time: 32MS
Language: Pascal		Result: Accepted

• Source Code

var
 a:array[0..100,0..100]of char;
 b,d,e:array[0..1000,0..1000]of longint;
 v:array[0..1000]of boolean;
 link:array[0..1000]of longint;
 r,c,num,n,i,j,ans:longint;

procedure signr;
 begin
  while a[i,j]='*' do
   begin
    b[i,j]:=num;
    inc(j);
    //if j>c then break;
   end;
 end;

procedure signc;
 begin
  while a[j,i]='*' do
   begin
    e[j,i]:=num;
    inc(j);
    //if j>r then break;
   end;
 end;

function dfs(p:longint):boolean;
 var
  i:longint;
 begin
  for i:=1 to d[p,0] do
   if (not v[d[p,i]])and(d[p,i]<>0) then//look out:d[p,i]<>0
    begin
     v[d[p,i]]:=true;
     if (link[d[p,i]]=0)or(dfs(link[d[p,i]])) then
      begin link[d[p,i]]:=p; exit(true); end;
    end;
  exit(false);
 end;

begin
 read(r,c);
 for i:=1 to r do
   for j:=1 to c do
    repeat read(a[i,j]); until (a[i,j]='.')or(a[i,j]='*');
 for i:=1 to r do//number the row
  for j:=1 to c do
   begin
    if a[i,j]='*' then inc(num);
    signr;
   end;
 n:=num;
 for i:=1 to c do//number the queue
  for j:=1 to r do
   begin
    if a[j,i]='*' then inc(num);
    signc;
   end;
 for i:=1 to r do//set up the map
  for j:=1 to c do
   if a[i,j]='*' then
    begin
     inc(d[b[i,j],0]);
     d[b[i,j],d[b[i,j],0]]:=e[i,j];
     inc(d[e[i,j],0]);
     d[e[i,j],d[e[i,j],0]]:=b[i,j];
    end;
 for i:=1 to n do
  begin
   fillchar(v,sizeof(v),0);
   if dfs(i) then inc(ans);
  end;
 writeln(ans);
end.

šš