bzoj2395

分组赛时学到的最小乘积生成树模型，感觉这个思路非常神，可以说是数形结合的经典问题

由于生成树有两个权值，我们把每个生成树的权值表示成点坐标（sa,sb)

显然我们知道，乘积最小，那么点必然落在下凸壳上

但由于点太多，graham之类要先知道所有点再求凸包的算法就失效了

于是我们使用quickhull算法，这个算法只要知道凸包上的两个点就可以扩展出下一个点，然后不断分治即可扩展出所有点

显然，以a为关键字和以b为关键字的最小生成树一定是凸包上的两个点i，j

根据quickhull算法，下一个凸包上的点就是离直线ij距离最大的点

转化一下，就是与ij垂直的向量点积最小的点

显然我们只要以此为关键字求最小生成树即可

这样我们不断分治下去，直到无法扩展为止，这样就找到了答案

但我好像被卡常了（还是写的太囧……），总之tle了……

 type node=record

        x,y,w,a,b:longint;

      end;

      point=record

        x,y:longint;

      end;

 var e:array[..] of node;

     fa:array[..] of longint;

     i,n,m:longint;

     ans,p1,p2:point;

 function getf(x:longint):longint;

   begin

     if fa[x]<>x then fa[x]:=getf(fa[x]);

     exit(fa[x]);

   end;

 procedure swap(var a,b:node);

   var c:node;

   begin

     c:=a;

     a:=b;

     b:=c;

   end;

 function cmp(x,y:node):boolean;

   begin

     if x.w=y.w then exit(x.a<y.a);

     exit(x.w<y.w);

   end;

 procedure sort(l,r:longint);

   var i,j:longint;

       x:node;

   begin

     i:=l;

     j:=r;

     x:=e[(l+r) shr ];

     repeat

       while cmp(e[i],x) do inc(i);

       while cmp(x,e[j]) do dec(j);

       if not(i>j) then

       begin

         swap(e[i],e[j]);

         inc(i);

         dec(j);

       end;

     until i>j;

     if l<j then sort(l,j);

     if i<r then sort(i,r);

   end;

 function mintree:point;

   var i,j,sa,sb,x,y:longint;

   begin

    {for j:=1 to m do

     writeln(e[j].w);  }

     j:=;

     sa:=;

     sb:=;

     for i:= to n do

       fa[i]:=i;

     i:=;

     while i<n- do

     begin

       inc(j);

       x:=getf(e[j].x);

       y:=getf(e[j].y);

       if x<>y then

       begin

         fa[x]:=y;

         sa:=sa+e[j].a;

         sb:=sb+e[j].b;

         inc(i);

       end;

     end;

     mintree.x:=sa;

     mintree.y:=sb;

     if (int64(ans.x)*int64(ans.y)>int64(sa)*int64(sb)) or (int64(ans.x)*int64(ans.y)=int64(sa)*int64(sb)) and (ans.x>sa) then

     begin

       ans.x:=sa;

       ans.y:=sb;

     end;

   end;

 function cross(a,b,c:point):int64;

   begin

     exit(int64(a.x-c.x)*int64(b.y-c.y)-int64(a.y-c.y)*int64(b.x-c.x));

   end;

 procedure work(p1,p2:point);

   var i:longint;

       p:point;

   begin

     for i:= to m do

       e[i].w:=e[i].a*(p1.y-p2.y)+e[i].b*(p2.x-p1.x);

     sort(,m);

     p:=mintree;

     if cross(p2,p,p1)>= then exit;

     work(p1,p);

     work(p,p2);

   end;

 begin

   readln(n,m);

   for i:= to m do

   begin

     readln(e[i].x,e[i].y,e[i].a,e[i].b);

     inc(e[i].x);

     inc(e[i].y);

     e[i].w:=e[i].a;

   end;

   ans.x:=;

   ans.y:=;

   sort(,m);

   p1:=mintree;

   for i:= to m do

     e[i].w:=e[i].b;

   sort(,m);

   p2:=mintree;

   work(p1,p2);

   writeln(ans.x,' ',ans.y);

 end.

巴特西

bzoj2395

最新文章

热门文章