首页 > 代码库 > BZOJ1443 游戏game (二分图染色+匈牙利算法)

BZOJ1443 游戏game (二分图染色+匈牙利算法)

先对整幅图进行二分图染色,再跑一遍匈牙利算法。如果最大匹配数=点数*2,那么输出WIN。

对于任何一个非必须在最大匹配上的点,即为所求的点。

  1 Program Test375num2;  2 type arr=record  3         u,v,next:longint;  4         end;  5 const dx:array[1..4] of longint=(0,0,-1,1);  6       dy:array[1..4] of longint=(1,-1,0,0);  7       maxn=100008;  8       maxm=maxn*4;  9 var map:array[0..108,0..108] of longint; 10     cl:array[0..maxn] of longint; 11     eg:array[0..maxm] of arr; 12     last:array[0..maxn] of longint; 13     l,r,f:array[0..maxn] of longint; 14     pd:array[0..maxn] of boolean; 15     i,j,m,n,num,sum,x:longint; 16     ch:char; 17 procedure dfs(i,j,w:longint); 18 var k,x,y:longint; 19 begin 20     cl[map[i,j]]:=w; 21     for k:=1 to 4 do 22     begin 23         x:=i+dx[k]; y:=j+dy[k]; 24         if (map[x,y]>0) and (cl[map[x,y]]=0) then 25             dfs(x,y,3-w); 26     end; 27 end; 28 procedure add(u,v:longint); 29 begin 30     inc(sum); 31     eg[sum].u:=u; 32     eg[sum].v:=v; 33     eg[sum].next:=last[u]; 34     last[u]:=sum; 35 end; 36 procedure put(i,j:longint); 37 var k,x,y:longint; 38 begin 39     for k:=1 to 4 do 40     begin 41         x:=i+dx[k]; y:=j+dy[k]; 42         if (map[x,y]>0) then add(map[i,j],map[x,y]); 43     end; 44 end; 45 function Hungarian(u:longint):boolean; 46 var i,v:longint; 47 begin 48     i:=last[u]; 49     while i<>0 do 50     begin 51         v:=eg[i].v; 52         if not pd[v] then 53         begin 54             pd[v]:=true; 55             if (l[v]=0) or Hungarian(l[v]) then 56             begin 57                 r[u]:=v; 58                 l[v]:=u; 59                 exit(true); 60             end; 61         end; 62         i:=eg[i].next; 63     end; 64     exit(false); 65 end; 66 procedure dfsl(u:longint); 67 var i,v:longint; 68 begin 69     f[u]:=2; 70     i:=last[u]; 71     while i<>0 do 72     begin 73         v:=eg[i].v; 74         if f[v]=0 then 75         begin 76             f[v]:=1; 77             if f[l[v]]=0 then dfsl(l[v]); 78         end; 79         i:=eg[i].next; 80     end; 81 end; 82  83 procedure dfsr(u:longint); 84 var i,v:longint; 85 begin 86     f[u]:=2; 87     i:=last[u]; 88     while i<>0 do 89     begin 90         v:=eg[i].v; 91         if f[v]=0 then 92         begin 93             f[v]:=1; 94             if f[r[v]]=0 then dfsr(r[v]); 95         end; 96         i:=eg[i].next; 97     end; 98 end; 99 begin100     readln(m,n);101     num:=0; sum:=0;102     for i:=1 to m do103     begin104         for j:=1 to n do105         begin106             read(ch);107             if ch=. then108             begin109                 map[i,j]:=(i-1)*n+j;110                 inc(num);111             end112             else map[i,j]:=-1;113         end;114         readln;115     end;116     for i:=1 to m do117         for j:=1 to n do118             if (map[i,j]>0) and (cl[map[i,j]]=0) then119                 dfs(i,j,1);120     for i:=1 to m do121         for j:=1 to n do122                         if map[i,j]>0 then put(i,j);123 124     fillchar(l,sizeof(l),0);125     fillchar(r,sizeof(r),0);126         sum:=0;127     for i:=1 to m*n do128         if cl[i]=1 then129         begin130             fillchar(pd,sizeof(pd),false);131              if Hungarian(i) then inc(sum);132         end;133     if sum*2=num then134     begin135         writeln(LOSE);136         halt;137     end;138     writeln(WIN);139     fillchar(f,sizeof(f),0);140     for i:=1 to m*n do141         if (cl[i]>0) and (f[i]=0) and (l[i]=0) and (r[i]=0) then142             if cl[i]=1 then dfsl(i) else dfsr(i);143     for i:= 1 to m do144         for j:=1 to n do145         begin146             x:=(i-1)*m+j;147             if f[x]=2 then writeln(i, ,j);148         end;149 end.

 ps:好像没有LOSE的点 ←_ ←

BZOJ1443 游戏game (二分图染色+匈牙利算法)