记录编号	276384	评测结果	AAAAAAAAAAAAAA
题目名称	[CTSC 2001]终极情报网	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2016-07-03 20:49:10	内存使用	6.05 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=310;
const int maxm=250010;
const double eps=1e-12;
const int INF=1000000000;
int cnt=1,fir[maxn],path[maxn];
int n,k,to[maxm],nxt[maxm],cap[maxm];

long double val[maxm],dis[maxn];

void addedge(int a,int b,int c,double v){
	nxt[++cnt]=fir[a];
	fir[a]=cnt;
	cap[cnt]=c;
	val[cnt]=v;
	to[cnt]=b;
}

queue<int>q;
int vis[maxn];
long double BFS(int S,int T){
	vis[S]=1;q.push(S);
	for(int i=S+1;i<=T;i++)
		dis[i]=0;dis[S]=1;
	while(!q.empty()){
		int x=q.front();q.pop();vis[x]=0;
		for(int i=fir[x];i;i=nxt[i])
			if(cap[i]&&eps<dis[x]*val[i]-dis[to[i]]){
				dis[to[i]]=dis[x]*val[i];
				if(!vis[to[i]])q.push(to[i]);
				vis[to[i]]=1;path[to[i]]=i;
			}
	}
	return dis[T];
}

int Aug(int S,int T){
	int f=INF,p=T;
	while(p!=S){
		f=min(f,cap[path[p]]);
		p=to[path[p]^1];
	}
	p=T;
	while(p!=S){
		cap[path[p]]-=f;
		cap[path[p]^1]+=f;
		p=to[path[p]^1];
	}
	return f;
}

long double MCMF(int S,int T){
	int f,totf=0;
	long double ret=1.0,d;
	while((d=BFS(S,T))>eps){
		f=Aug(S,T);totf+=f;
		while(f--)ret*=d;
	}
	return totf==k?ret:0.0;
}

void Print(long double ans){
	char s[50];
	sprintf(s,"%.15Lf\n",ans);
	int p=0,tot=0;
	while(tot<5){
		if(s[p]!='0'&&s[p]!='.'||tot)
			tot+=1;
		p++;	
	}
	if(s[p]>='5')s[p-1]+=1;
	s[p]='\000';printf("%s",s);
}

int C[maxn];
long double P[maxn];
int main(){
#ifndef ONLINE_JUDGE
	freopen("agent.in","r",stdin);
	freopen("agent.out","w",stdout);
#endif
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%Lf",&P[i]);
	for(int i=1;i<=n;i++)scanf("%d",&C[i]);
	
	for(int i=1;i<=n;i++){
		if(C[i]>0&&P[i]>eps){
			addedge(n+1,i,C[i],P[i]);
			addedge(i,n+1,0,1/P[i]);
		}
	}
	for(int i=1,c;i<=n;i++){
		scanf("%d",&c);
		if(c>0){
			addedge(i,n+2,INF,1);
			addedge(n+2,i,0,1);
		}
	}
	 
	int a,b,c;
	long double p;
	while(true){
		scanf("%d%d",&a,&b);
		if(a==-1&&b==-1)break;
		scanf("%Lf%d",&p,&c);
		addedge(a,b,c,p);
		addedge(b,a,0,1/p);
		addedge(b,a,c,p);
		addedge(a,b,0,1/p);
	}
	addedge(0,n+1,k,1);
	addedge(n+1,0,0,1);
	long double ans=MCMF(0,n+2);
	if(ans>eps)Print(ans);
	else printf("0\n");
	return 0;	
}