BZOJ2542: [Ctsc2001]终极情报网
题解:
乘积最小只需要取对数。然后反向边就变成1/c,而不是-c了。
精度问题搞得我已经我想说什么了。。。
贴一份网上的pascal
代码;
type ss=record
x,y,c,r,next:longint;
f:extended;
end;
const maxn=; maxm=; qu=; oo=maxlongint shr ;
var i,j,n,cnt,st,ed,w,tot,t1,t2,t4,k,t,h,flow,augo,hh,tt:longint;
pr:string;
s,x:array[..maxn] of extended;
y,pre,b:array[..maxn] of longint;
f:array[..maxn] of boolean;
e:array[..maxm] of ss;
q:array[..qu] of longint;
ans,t3,cost:extended;
procedure jia(x,y,c:longint;f:extended);
begin
inc(tot); e[tot].x:=x; e[tot].y:=y; e[tot].c:=c; e[tot].f:=f;
e[tot].next:=b[x]; b[x]:=tot;
inc(tot); e[tot].x:=y; e[tot].y:=x; e[tot].f:=-f;
e[tot].next:=b[y]; b[y]:=tot;
e[tot].r:=tot-; e[tot-].r:=tot;
end;
begin
readln(n,k);
for i:= to n do read(x[i]);
for i:= to n do read(y[i]);
st:=n+; ed:=n+; cnt:=n+; fillchar(b,sizeof(b),);
jia(st,cnt,k,);
for i:= to n do
if y[i]> then jia(cnt,i,y[i],-ln(x[i]));
for i:= to n do
begin
read(t);
if t= then jia(i,ed,oo,);
end;
while true do
begin
read(t1,t2);
if t1=- then break;
readln(t3,t4);
jia(t1,t2,t4,-ln(t3));
jia(t2,t1,t4,-ln(t3));
end;
ans:=;
while true do
begin
for i:= to cnt do s[i]:=oo;
h:=; t:=; q[]:=st; s[st]:=; hh:=; tt:=;
repeat
w:=q[h]; f[w]:=false; i:=b[w];
inc(h); inc(hh); h:=h mod qu;
while i<>- do
begin
if (s[e[i].y]-s[w]-e[i].f>1e-12) and (e[i].c>) then
begin
s[e[i].y]:=s[w]+e[i].f;
pre[e[i].y]:=i;
if not(f[e[i].y]) then
if s[e[i].y]<s[q[h]] then
begin
dec(h); dec(hh);
if h< then h:=qu-;
q[h]:=e[i].y;
end
else
begin
inc(t); inc(tt);
t:=t mod qu;
q[t]:=e[i].y;
end;
f[e[i].y]:=true;
end;
i:=e[i].next;
end;
until hh>tt;
if s[ed]=oo then break;
flow:=maxlongint;
i:=pre[ed];
while i<> do
begin
if flow>e[i].c then flow:=e[i].c;
i:=pre[e[i].x];
end;
i:=pre[ed]; cost:=;
while i<> do
begin
cost:=e[i].f+cost; dec(e[i].c,flow);
inc(e[e[i].r].c,flow); i:=pre[e[i].x];
end;
for i:= to flow do ans:=ans*exp(-cost);
inc(augo,flow);
end;
if augo<k then writeln() else
begin
write('0.'); ans:=ans*;
while ans< do
begin
ans:=ans*;
write();
end;
for i:= to do ans:=ans*;
for i:= to do ans:=round(ans/);
writeln(trunc(ans));
end;
end.
2542: [Ctsc2001]终极情报网
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 211 Solved: 85
[Submit][Status]
Description
在最后的诺曼底登陆战开始之前,盟军与德军的情报部门围绕着最终的登陆地点展开了一场规模空前的情报战。
这场情报战中,盟军的战术是利用那些潜伏在敌军内部的双重间谍,将假的登陆消息发布给敌军的情报机关的负责人。那些已经潜入敌后的间谍们都是盟军情报部的精英,忠实可靠;但是如何选择合适的人选,以及最佳的消息传递方法,才能保证假消息能够尽快而且安全准确地传递到德军指挥官们的耳朵里,成了困扰盟军情报部长的最大问题。他需要你的帮助。
以下是情报部长提供的作战资料:
在敌后一共潜伏着我方最优秀的N名间谍,分别用数字1, 2, …, N编号。在给定的作战时间内,任意两人之间至多只进行一次点对点的双人联系。
我将给你一份表格,表格中将提供任意两位间谍i和j之间进行联系的安全程度,用一个 [0, 1] 的实数Si j表示;以及他们这次联系时,能够互相传递的消息的最大数目,用一个正整数表示Mi j (如果在表格中没有被提及,那么间谍i和j之间不进行直接联系)。
假消息从盟军总部传递到每个间谍手里的渠道也不是绝对安全,我们用 [0, 1] 的实数ASj表示总部与间谍j之间进行联系的安全程度,AMj则表示总部和间谍j之间进行联系时传递的消息的最大数目。对于不和总部直接联系的间谍,他的AMj=0(而表格中给出的他的ASj是没有意义的)。
当然,假消息从间谍手中交到敌军的情报部官员的办公桌上的过程是绝对安全的,也即是说,间谍与敌军情报部门之间要么不进行直接联系,要么其联系的安全程度是1(即完全可靠)。
现在情报部打算把K条假消息“透露”到德军那里。消息先由总部一次性发给N名间谍中的一些人,再通过他们之间的情报网传播,最终由这N名间谍中的某些将情报送到德军手中。
对于一条消息,只有安全的通过了所有的中转过程到达敌军情报部,这个传递消息的过程才算是安全的;因此根据乘法原理,它的安全程度P就是从总部出发,经多次传递直到到达德军那里,每一次传递该消息的安全程度的乘积。
而对于整个计划而言,只有当N条消息都安全的通过情报网到达德军手中,没有一条引起怀疑时,才算是成功的。所以计划的可靠程度是所有消息的安全程度的乘积。
显然,计划的可靠性取决于这些消息在情报网中的传递方法。
我需要一个方案,确定消息应该从哪些人手中传递到哪些人手中,使得最终计划的可靠性最大。
你可以利用计算机,来求得这个最可靠的消息传递方案。
Input
第一行包括两个整数N和K,分别是间谍的总人数和计划包含的消息总数。
第二行包括2N个数,前N个数是实数AS1, AS2, …, ASN(范围在[0, 1]以内);后N个数是整数AM1, AM1, …, AMN。
第三行包含了N个整数,其中第i(i = 1, 2, …, N)个整数如果为0表示间谍i与德军情报部不进行联系,如果为1则表示间谍与德军情报部进行联系。
第四行开始,每行包括4个数,依次分别是:代表间谍编号的正整数i和j,间谍i和j联系的安全性参数Si j([0,1]范围内的实数),以及i、j之间传递的最大消息数 Mi j(每一行的i均小于j )。
最后的一行包含两个整数-1 -1,表示输入数据的结束。
0
Output
只有一行。这一行中包含一个实数P,给出的是整个计划的可靠程度P,保留5位有效数字(四舍五入)。
如果情报网根本不能将K条消息传到德军手中,那么计划的可靠性为0。
(你可以假定,如果计划存在,那么它的可靠性大于1e-12)
Sample Input
0.9 0.7 0.8 0 0 0 2 6 8 0 0 0
0 0 0 1 0 1
1 4 0.5 2
2 3 0.9 5
2 5 0.8 2
2 6 0.8 7
3 5 0.8 2
5 6 0.8 4
-1 -1
Sample Output
最新文章
- filesort是通过相应的排序算法
- Elasticsearch升级1.5版本暴露jdk的bug
- TeX Live安装配置等默认目录
- October 12th 2016 Week 42nd Wednesday
- 第42讲:Scala中泛型类、泛型函数、泛型在Spark中的广泛应用
- 2天驾驭DIV+CSS (实战篇)(转)
- 297 - Quadtrees (UVa)
- 【Android平台安全方案】の #00-请不要在外部存储(SD卡)加密存储的敏感信息
- 最简单的MFC
- php curl调用相关api
- javascipt : filter
- Maven工具的介绍,配置及使用
- 【读书笔记】【深入理解ES6】#2-字符串和正则表达式
- Vue针对性笔记
- Python —— 函数高级特性(切片、迭代、列表生成式、生成器、迭代器)
- 7、Curator的常规操作
- android app 流量统计
- vue.js 作一个用户表添加页面----初级
- Win7下无法启动sql server fulltext search (mssqlserver)的问题
- Android常用库和插件
热门文章
- 在系统方法中调用navigationController的标准写法
- Contest2037 - CSU Monthly 2013 Oct (problem B :Scoop water)
- .NET Json 解析到Dictionary,原生代码
- 【数学】[BZOJ 3884] 上帝与集合的正确用法
- eclipse中切换jre后报错:Java compiler level does not match the version of the installed Java project facet.
- PHP中CURL方法curl_setopt()函数的一些参数 (转)
- JAVA面试题:String 堆内存和栈内存
- URAL 1012 K-based Numbers. Version 2(DP+高精度)
- http://nxlhero.blog.51cto.com/962631/1666250?plg_nld=1&;plg_uin=1&;plg_auth=1&;plg_nld=1&;plg_usr=1&;plg_vkey=1&;plg_dev=1
- html--offsetLeft,Left,clientLeft的关键--动态获取计算元素位置关系