首页 > 代码库 > bzoj 3035 pascal

bzoj 3035 pascal

2024-07-11 13:31:08   220人阅读

这道题也是一个二分图匹配的题，也需要用匈牙利算法，但需要小小的改进

 

中间需要一个二分搜答案的过程，这也是其中的一个小小的变型吧

 

需要注意一下读入，他是有分钟有秒，所以不要被坑哦

 

最后不说废话，直接上代码

 

/**************************************************************
    Problem: 3035
    User: Davidliu
    Language: Pascal
    Result: Accepted
    Time:236 ms
    Memory:4216 kb
****************************************************************/
 
var
 
    n, m, t2, v                     :longint;
 
    t1                              :real;
 
    dis                             :array[0..100,0..100] of real;
 
    ans                             :real;
 
    pre, other, last                :array[0..200100] of longint;
 
    link                            :array[0..100] of longint;
 
    flag                            :array[0..100] of boolean;
 
    x1, x2, y1, y2                  :array[0..100] of longint;
 
    l                               :longint;
 
    len                             :array[0..200100] of real;
 
 
 
procedure init;
 
var
 
    i, j                            :longint;
 
begin
 
    read(n,m,t1,t2,v);
 
    for i:=1 to m do read(x2[i],y2[i]);
 
    for i:=1 to n do read(x1[i],y1[i]);
 
    t1:=t1/60;
 
    for i:=1 to n do
 
        for j:=1 to m do
 
            dis[i,j]:=sqrt((x1[i]-x2[j])*(x1[i]-x2[j])+(y1[i]-y2[j])*(y1[i]-y2[j]));
 
end;
 
 
 
procedure connect(x,y:longint; z:real);
 
begin
 
    inc(l);
 
    pre[l]:=last[x];
 
    last[x]:=l;
 
    other[l]:=y;
 
    len[l]:=z;
 
end;
 
 
 
function find(i:longint):boolean;
 
var
 
    q, p                            :longint;
 
begin
 
    q:=last[i];
 
    while q<>0 do
 
    begin
 
        p:=other[q];
 
        if (not flag[p]) then
 
        begin
 
            flag[p]:=true;
 
            if (link[p]=0) or (find(link[p])) then
 
            begin
 
                link[p]:=i;
 
                exit(true);
 
            end;
 
        end;
 
        q:=pre[q];
 
    end;
 
    exit(false);
 
end;
 
 
 
procedure judge(low,high:real);
 
var
 
    mid                             :real;
 
    tot                             :longint;
 
    i, j, ll                        :longint;
 
    k                               :longint;
 
    count                           :longint;
 
begin
 
    if high<low then exit;
 
    fillchar(last,sizeof(last),0);
 
    fillchar(link,sizeof(link),0);
 
    tot:=0;
 
    l:=1;
 
    mid:=(low+high)/2;
 
    k:=trunc(((mid-t1)/(t1+t2))+1);
 
    for i:=1 to n do
 
        for ll:=1 to k do
 
        begin
 
            inc(tot);
 
            for j:=1 to m do
 
                if (((mid-t1)-(ll-1)*(t1+t2))*v)>=dis[i,j]
 
                    then connect(tot,j,dis[i,j]/v+(ll-1)*(t1+t2)+t1);
 
        end;
 
    count:=0;
 
 
 
    for i:=1 to tot do
 
    begin
 
        fillchar(flag,sizeof(flag),false);
 
        if find(i) then inc(count);
 
    end;
 
 
 
    if (high-low<1e-8) then
 
        if count>=m then
 
        begin
 
            ans:=mid;
 
        end else exit;
 
    if count>=m then
 
    begin
 
        ans:=mid;
 
        judge(low,mid-1e-8);
 
    end else judge(mid+1e-8,high);
 
end;
 
 
 
procedure main;
 
begin
 
    judge(1,30000);
 
    writeln(ans:0:6);
 
end;
 
 
 
begin
 
    init;
 
    main;
 
end.


联系
我们