bzoj3140

首先考虑二维的情况

min(x,y)也就意味着确定最小后，另外一维肯定打满

然后最小那个如果是k的话就相当于用k*1次——这不就是行列覆盖吗，二分图秒之

三维呢？考虑到a*b*c<=5000也就是最小的那维不超过17

那么我们直接穷举那维用哪些，然后另外的就跟二维一样了

注意要优化常数

 type node=record

        po,next:longint;

      end;

 var e:array[..] of node;

     d:array[..,..] of longint;

     p,cx,cy:array[..] of longint;

     v:array[..] of boolean;

     can,f:array[..] of boolean;

     x,tt,j,k,len,ans,i,t,a,b,c,a0,b0,c0:longint;

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

   begin

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

   end;

 procedure add(x,y:longint);

   begin

     inc(len);

     e[len].po:=y;

     e[len].next:=p[x];

     p[x]:=len;

   end;

 procedure swap(var a,b:longint);

   var c:longint;

   begin

     c:=a;

     a:=b;

     b:=c;

   end;

 function dfs(x:longint):longint;

   var i,y:longint;

   begin

     i:=p[x];

     while i<> do

     begin

       y:=e[i].po;

       if not v[y] then

       begin

         v[y]:=true;

         if (cy[y]=-) or (dfs(cy[y])=) then

         begin

           cy[y]:=x;

           cx[x]:=y;

           exit();

         end;

       end;

       i:=e[i].next;

     end;

     exit();

   end;

 function cal(s:longint):longint;

   var i,j:longint;

   begin

     cal:=s;

     len:=;

     for i:= to b do

     begin

       p[i]:=;

       cx[i]:=-;

     end;

     for i:= to c do

       cy[i]:=-;

     for i:= to t do

       if not f[d[i,a0]] then

         add(d[i,b0],d[i,c0]);

     for i:= to b do

       if cx[i]=- then

       begin

         for j:= to c do

           v[j]:=false;

         cal:=cal+dfs(i);

         if cal>=ans then exit;

       end;

   end;

 procedure work(x,s:longint);

   var m:longint;

   begin

     if s>=ans then exit;

     if x=a+ then

     begin

       m:=cal(s);

       if m<ans then ans:=m;

     end

     else begin

       f[x]:=false;

       work(x+,s);

       if can[x] then

       begin

         f[x]:=true;

         work(x+,s+);

         f[x]:=false;

       end;

     end;

   end;

 begin

   readln(tt);

   while tt> do

   begin

     dec(tt);

     readln(a,b,c);

     a0:=; b0:=; c0:=;

     t:=;

     for i:= to a do

       for j:= to b do

         for k:= to c do

         begin

           read(x);

           if x= then

           begin

             inc(t);

             d[t,]:=i;

             d[t,]:=j;

             d[t,]:=k;

           end;

         end;

     if (b<=a) and (b<=c) then

     begin

       swap(a0,b0);

       swap(a,b);

     end

     else if (c<=a) and (c<=b) then

     begin

       swap(a0,c0);

       swap(a,c);

     end;

     if b>c then

     begin

       swap(b0,c0);

       swap(b,c);

     end;

     fillchar(can,sizeof(can),false);

     for i:= to t do

       can[d[i,a0]]:=true;

     ans:=;

     for i:= to a do

       if can[i] then inc(ans);

     fillchar(f,sizeof(f),false);

     work(,);

     writeln(ans);

   end;

 end.

巴特西

bzoj3140

最新文章

热门文章