bzoj4080

分组赛时wy大神讲的题，网上都是随机化的题解

我来讲一下正解吧，我们穷举两个点，这两点距离要小于限制

然后我们分别以这两个点为圆心，两点距离为半径画圆

圆圆相交的部分被两点练成线段划分成两部分，不难发现

每个部分内点点之间的距离是小于限制的，很明显想到二分图

对于上半部分与下半部分的两点，如果距离大于限制则连边

然后我们求最大点独立集即可

求最大独立集的方案各种想错，实在太SB

做完最大匹配后首先先把未匹配的点拉出来，然后把他们有边相连的点都标记

然后处理每对匹配，若一个点被标记则选另一个点

这样是不可能出现两个点都标记的匹配，因为这样就会出现一条增广路，与最大匹配矛盾

type node=record

       po,next:longint;

     end;

var e,ee:array[..] of node;

    q,q1,q2,c,x,y,cy,cx,p:array[..] of longint;

    v,v1,v2:array[..] of boolean;

    z,ll,d,t1,t2,i,j,k,l,ans,len,n:longint;

procedure add(x,y:longint);

  begin

    inc(len);

    e[len].po:=y;

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

    p[x]:=len;

    ee[len].po:=x;

    ee[len].next:=q[y];

    q[y]:=len;

  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 match:longint;

  var i:longint;

  begin

    fillchar(cy,sizeof(cy),);

    fillchar(cx,sizeof(cx),);

    match:=t1+t2;

    if (t2=) or (t1=) then exit;

    for i:= to t1 do

      if cx[i]=- then

      begin

        fillchar(v,sizeof(v),false);

        match:=match-dfs(i);

      end;

  end;

function cross(i,j,k:longint):longint;

  begin

    exit((x[i]-x[k])*(y[j]-y[k])-(x[j]-x[k])*(y[i]-y[k]));

  end;

function dis(i,j:longint):longint;

  begin

    exit(sqr(x[i]-x[j])+sqr(y[i]-y[j]));

  end;

begin

  readln(n,d);

  d:=d*d;

  for i:= to n do

    readln(x[i],y[i]);

  ans:=;

  c[]:=;

  for i:= to n- do

    for j:=i+ to n do

      if dis(i,j)<=d then

      begin

        ll:=dis(i,j);

        t1:=;

        t2:=;

        fillchar(p,sizeof(p),);

        fillchar(q,sizeof(q),);

        len:=;

        for k:= to n do

          if (dis(i,k)<=ll) and (dis(j,k)<=ll) then

          begin

            if cross(k,j,i)>= then

            begin

              inc(t1);

              q1[t1]:=k;

            end

            else begin

              inc(t2);

              q2[t2]:=k;

            end;

          end;

        for k:= to t1 do

          for l:= to t2 do

            if dis(q1[k],q2[l])>d then add(k,l);

        l:=match;

        if l>ans then

        begin

          ans:=;

          fillchar(v1,sizeof(v1),false);

          fillchar(v2,sizeof(v2),false);

          for k:= to t1 do

            if cx[k]=- then

            begin

              inc(ans);

              c[ans]:=q1[k];

              z:=p[k];

              while z<> do

              begin

                v2[e[z].po]:=true;

                z:=e[z].next;

              end;

            end;

          for k:= to t2 do

            if cy[k]=- then

            begin

              inc(ans);

              c[ans]:=q2[k];

              z:=q[k];

              while z<> do

              begin

                v1[ee[z].po]:=true;

                z:=ee[z].next;

              end;

            end;

          for k:= to t1 do

            if cx[k]<>- then

            begin

              inc(ans);

              if not v1[k] then c[ans]:=q1[k]

              else c[ans]:=q2[cx[k]];

            end;

        end;

      end;

  writeln(ans);

  for i:= to ans do

    write(c[i],' ');

  writeln;

end.

巴特西

bzoj4080

最新文章

热门文章