bzoj 3035 二分答案+二分图最大匹配
2024-09-21 21:22:50
大原来做的一道题,偷懒直接粘的原来的程序
http://www.cnblogs.com/BLADEVIL/p/3433520.html
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
n, m, t2, v :longint;
t1 :real;
dis :array[..,..] of real;
ans :real;
pre, other, last :array[..] of longint;
link :array[..] of longint;
flag :array[..] of boolean;
x1, x2, y1, y2 :array[..] of longint;
l :longint;
len :array[..] of real;
procedure init;
var
i, j :longint;
begin
read(n,m,t1,t2,v);
for i:= to m do read(x2[i],y2[i]);
for i:= to n do read(x1[i],y1[i]);
t1:=t1/;
for i:= to n do
for j:= 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<> do
begin
p:=other[q];
if (not flag[p]) then
begin
flag[p]:=true;
if (link[p]=) 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),);
fillchar(link,sizeof(link),);
tot:=;
l:=;
mid:=(low+high)/;
k:=trunc(((mid-t1)/(t1+t2))+);
for i:= to n do
for ll:= to k do
begin
inc(tot);
for j:= to m do
if (((mid-t1)-(ll-)*(t1+t2))*v)>=dis[i,j]
then connect(tot,j,dis[i,j]/v+(ll-)*(t1+t2)+t1);
end;
count:=;
for i:= 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(,);
writeln(ans::);
end;
begin
init;
main;
end.
最新文章
- ES6之解构赋值
- 【皇甫】☀Hibernate入门
- jquery.cookie.js使用
- keil uvision看厌了么?试试Sublime Text吧!
- React-Flux 介绍及实例演示
- CentOS 6.4 文件夹打开方式
- linux中如何查看某一进程的启动时间
- postgresql 抽样查询
- 开涛spring3(6.9) - AOP 之 6.9 代理机制
- [转载]Reids配置文件详解
- 一起写框架-Ioc内核容器的实现-基础功能-容器对象名默认首字母小写(八)
- 实战开发-》融云tp3.2.3
- call、apply、bind
- const修饰指针+volatile +restrict
- 2018-2019-20175334实验一《Java开发环境的熟悉》实验报告
- sqlserver全文检索
- Win7 VS2017 NASM编译FFMPEG(2018.12.22)
- 离线部署 pm2
- day39 mysql数据库基本操作
- 使用Java打印字符串表格(中英文内容不乱)
热门文章
- JTS空间分析工具包(GIS开源)学习 JAVA
- MySQL加密算法
- MenuStrip的自动显示
- [剑指Offer] 47.求1+2+3+...+n
- 反向传播算法 Backpropagation Algorithm
- 【bzoj4550】小奇的博弈 博弈论+dp
- 洛谷 P2757 [国家集训队]等差子序列 解题报告
- UVA.455 Periodic Strings(字符串的最小周期)
- MyBatis之二级缓存
- apache的作用和tomcat的区别