测试数据 #0: Accepted, time = 15 ms, mem = 20008 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 20012 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 20012 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 20012 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 20008 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 20012 KiB, score = 10
测试数据 #6: Accepted, time = 250 ms, mem = 20016 KiB, score = 20
测试数据 #7: Accepted, time = 859 ms, mem = 20016 KiB, score = 20
Accepted, time = 1200 ms, mem = 20016 KiB, score = 100
这个题输出及其麻烦 真是蛋疼
void MinCostMaxFlow()
{
int nannan;
int lovenannan=0;
while(Spfa())Adjust();
ans=exp(-ans);
while(ans<0.99999999999999999)ans=ans*10,lovenannan++;
if(lovenannan>0)
{
printf("0.");
for(int i=1;i<lovenannan-1;i++)printf("0");
ans=ans*10000;
nannan=(int)ans;
if(ans-nannan>0.5)nannan++;
if(nannan<100000)
{
if(lovenannan!=1)printf("0");
printf("%d",nannan);
}
else printf("%d",nannan/10);
}
else printf("1.0000");
}

算了，将就一下吧

为什么会这样。。。

。。。

贴个程序晾凉。。。
type ss=record
x,y,c,r,next:longint;
f:extended;
end;
const maxn=401; maxm=46001; qu=10000; oo=maxlongint shr 2;
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[0..maxn] of extended;
y,pre,b:array[0..maxn] of longint;
f:array[0..maxn] of boolean;
e:array[0..maxm] of ss;
q:array[0..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-1; e[tot-1].r:=tot;
end;
begin
readln(n,k);
for i:=1 to n do read(x[i]);
for i:=1 to n do read(y[i]);
st:=n+1; ed:=n+2; cnt:=n+3; fillchar(b,sizeof(b),255);
jia(st,cnt,k,0);
for i:=1 to n do
if y[i]>0 then jia(cnt,i,y[i],-ln(x[i]));
for i:=1 to n do
begin
read(t);
if t=1 then jia(i,ed,oo,0);
end;
while true do
begin
read(t1,t2);
if t1=-1 then break;
readln(t3,t4);
jia(t1,t2,t4,-ln(t3));
jia(t2,t1,t4,-ln(t3));
end;
ans:=1;
while true do
begin
for i:=1 to cnt do s[i]:=oo;
h:=1; t:=1; q[1]:=st; s[st]:=0; hh:=1; tt:=1;
repeat
w:=q[h]; f[w]:=false; i:=b[w];
inc(h); inc(hh); h:=h mod qu;
while i<>-1 do
begin
if (s[e[i].y]-s[w]-e[i].f>1e-12) and (e[i].c>0) 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<0 then h:=qu-1;
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<>0 do
begin
if flow>e[i].c then flow:=e[i].c;
i:=pre[e[i].x];
end;
i:=pre[ed]; cost:=0;
while i<>0 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:=1 to flow do ans:=ans*exp(-cost);
inc(augo,flow);
end;
if augo<k then writeln(0) else
begin
write('0.'); ans:=ans*10;
while ans<1 do
begin
ans:=ans*10;
write(0);
end;
for i:=1 to 10 do ans:=ans*10;
for i:=1 to 6 do ans:=round(ans/10);
writeln(trunc(ans));
end;
end.

http://hi.baidu.com/macaulish64/item/7d8a97f72961eb37a729885a
如果你只过了前5个点，那个恭喜你，程序应该是没有错的，错的是浮点运算还是什么balabala的，就是精度问题，解决方法去看我空间吧！

稍微对反向弧的费用处理一下 取倒数是不要四舍五入 而是 退一 要不有可能出现负权环
挺慢的代码 不过算是A了
VijosEx via JudgeDaemon2/13.6.5.0 via libjudge
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1456 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1456 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1456 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1504 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1508 KiB, score = 10
测试数据 #5: Accepted, time = 3 ms, mem = 1620 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 1828 KiB, score = 20
测试数据 #7: Accepted, time = 140 ms, mem = 2464 KiB, score = 20
Accepted, time = 204 ms, mem = 2464 KiB, score = 100
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#include <vector>

using namespace std;

#define MAXN 500

const double detail=0.999999999999;

int n,k;

double as[MAXN];
int am[MAXN];

struct node {
int t,v;
double c;
node *next,*next0;
};

node *map[MAXN][MAXN];
node *head[MAXN];

int Insert(int s,int t,int f,double c){
if (map[s][t]==NULL){
node *p=new(node);
(*p).t=t;
(*p).c=c;
(*p).v=f;
(*p).next0=NULL;
(*p).next=head[s];
head[s]=p;
map[s][t]=p;
} else {
node *p=map[s][t];
while (p!=NULL){
if ((*p).c==c){
(*p).v+=f;
return 0;
}
p=(*p).next0;
}
p=new(node);
(*p).t=t;
(*p).v=f;
(*p).c=c;
(*p).next=head[s];
head[s]=p;
(*p).next0=map[s][t];
map[s][t]=p;
}
return 0;
}

double dist[MAXN],minc[MAXN];
int suff[MAXN],minf[MAXN];
bool f[MAXN];
int max_flow=0;

struct cmp{
bool operator()(int x, int y){
return dist[x]<dist[y];
}
};

priority_queue<int,vector<int>,cmp>qu;

double EXP(double x,int y){
if (y==1) return x;
return EXP(x,y/2)*EXP(x,y-(y/2));
}

double minimum_cost_flow(int s,int t){
double rec=1;
while (1){
memset(dist,0,sizeof(dist));
memset(f,false,sizeof(f));
f[s]=true;
dist[s]=1;
suff[s]=0;
minf[s]=0x7fffffff;
qu.push(s);
while (!qu.empty()){
int u=qu.top();
qu.pop();
if (f[u]){
f[u]=false;
node *p=head[u];
while (p!=NULL){
if ((p).v>0&&dist[u](*p).c>dist[(*p).t]){
dist[(p).t]=dist[u](*p).c;
suff[(*p).t]=u;
f[(*p).t]=true;
qu.push((*p).t);
minf[(*p).t]=min(minf[u],(*p).v);
minc[(*p).t]=(*p).c;
}
p=(p).next;
}
}
}
if (dist[t]){
max_flow+=minf[t];
int i=t;
while (suff[i]){
rec=EXP(minc[i],minf[t]);
Insert(suff[i],i,-minf[t],minc[i]);
Insert(i,suff[i],minf[t],double(1)/double(minc[i])*detail);
i=suff[i];
}
} else break;
}
return rec;
}

void output_double(double x,int y){
int i=0,l=0;
int ans[15];
ans[0]=0;
while (1){
x*=10;
int z=int(x);
x-=int(x);
ans[++l]=z;
if (z||i) i++;
if (i>=y+1) break;
}
if (ans[l]>=5) ans[l-1]++;
int j=l-1;
while (ans[j]>=10) {
ans[j-1]+=ans[j]/10;
ans[j]%=10;
j--;
}
printf("%d.",ans[0]);
for (int i=0;i++<l-1;) printf("%d",ans[i]);
printf("\n");
}

int main(){
scanf("%d%d",&n,&k);
for (int i=0;i<MAXN;i++){
head[i]=NULL;
for (int j=0;j<MAXN;j++){
map[i][j]=NULL;
}
}
for (int i=0;i++<n;) {
scanf("%lf",&as[i]);
}
for (int i=0;i++<n;) {
scanf("%d",&am[i]);
if (am[i]){
Insert(n+1,i,am[i],as[i]);
}
}
for (int i=0;i++<n;){
int x;
scanf("%d",&x);
if (x){
Insert(i,n+2,0x7fffffff,1);
}
}
while (1){
int x,y,m;
double s;
scanf("%d%d",&x,&y);
if (x==-1&&y==-1) break;
scanf("%lf%d",&s,&m);
Insert(x,y,m,s);
Insert(y,x,m,s);
}
Insert(n+3,n+1,k,1);
double ans=minimum_cost_flow(n+3,n+2);
if (max_flow<k) printf("0\n");
else output_double(ans,5);
return 0;
}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：50 有效耗时：0ms

为啥？？？ 精度造成的负环？？？

楼上误了，不是牛，是鱼。。。。

注意 浮点运算 精度 问题

可能会导致 出现 负圈……

多亏牛人提醒，否则这题 本菜 是 A不了 的。。。

米有什么人做？找找感觉吧

我做有关实数的题比较少

所以饱受精度的煎熬!!!

一直90，一直以为是Pascal的精度问题，后来发现写zkw费用流时标号部分少写一句话，囧...

Accepted 有效得分：100 有效耗时：0ms

spfaMS可以啊。。就是慢点。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 368ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：368ms

这题的输出真萎缩啊……

还有SPFA直接挂，改成zkw费用流就AC了……

算法艺术与信息学竞赛里面有

我上午还看到的呢

裸的费用流......

黑书是么？

那个《算法导论》还是刘汝佳写的《算法艺术》？

取对数最小费用

神题……

最小费用流……