记录编号	191918	评测结果	AAAAAAAAAAAAAA
题目名称	[CTSC 2001]终极情报网	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2015-10-09 09:07:29	内存使用	1.17 MiB

#include<cstdio>
#include<deque>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int SIZEN=310,SIZEK=110,maxn=0x7fffffff/2;
const double zero=1e-12;
int N,K,S,T,tot=0;
int key[SIZEN],mi[SIZEN],nowflow=0;
deque<int> s[SIZEN];
double ans=1.0;
double f[SIZEN];
class miku
{
public:
	int fr,to,cap,flow;
	double cost;
	miku(){}
	miku(int a,int b,int c,int d,double e)
	{
		fr=a,to=b,cap=c,flow=d,cost=e;
	}
}E[100*SIZEN];
void add(int fr,int to,int cap,double cost)
{
	s[fr].push_back(tot);
	E[tot++]=miku(fr,to,cap,0,cost);
	s[to].push_back(tot);
	E[tot++]=miku(to,fr,0,0,1.0/cost);
}
void read()
{
	scanf("%d%d",&N,&K);
	S=0;T=N+1;
	double AS[SIZEN];
	int AM[SIZEN];
	for(int i=1;i<=N;i++) scanf("%lf",&AS[i]);
	for(int i=1;i<=N;i++) scanf("%d",&AM[i]);
	for(int i=1;i<=N;i++) 
	{
		if(AM[i]!=0&&AS[i]>zero)
		add(S,i,AM[i],AS[i]);
	}
	int t;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&t);
		if(t!=0)
		add(i,T,maxn,1.0);
	}
	int fr,to,cap;
	double cost;
	while(true)
	{
		scanf("%d%d",&fr,&to);
		if(fr==-1||to==-1) break;
		scanf("%lf%d",&cost,&cap);
		add(fr,to,cap,cost);
		add(to,fr,cap,cost);
	}
}
bool SPFA()
{
	if(nowflow>=K) return 0;
	deque<int> Q;
	bool inq[SIZEN]={0};
	for(int i=S;i<=T;i++)
		f[i]=0.0,key[i]=-1,mi[i]=0;
	f[S]=1.0,inq[S]=1,Q.push_back(S);mi[S]=maxn;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();inq[x]=0;
		for(int i=0;i<s[x].size();i++)
		{
			miku &v=E[s[x][i]];
			if(v.cap<=v.flow) continue;
			if(f[x]*v.cost>f[v.to]+zero)
			{
				f[v.to]=f[x]*v.cost;
				key[v.to]=s[x][i];
				mi[v.to]=min(mi[x],v.cap-v.flow);
				if(!inq[v.to])
				{
					inq[v.to]=1;
					Q.push_back(v.to);
				}
			}
		}
	}
	if(f[T]<zero) return 0;
	return 1;
}
void dfs()
{
	int temp=T;
	int now=min(mi[T],K-nowflow);
	nowflow+=now;
	ans*=pow(f[T],now+0.0);
	while(temp!=S)
	{
		int t=key[temp];
		E[t].flow+=now;
		E[t^1].flow-=now;
		temp=E[t].fr;
	}
}
void print(double ans)
{
	char ch[40];
	sprintf(ch,"%.15lf\n",ans);
	int sum=0,i;
	for(i=0;sum<5;i++)
		if((ch[i]!='0'&&ch[i]!='.')||sum>0) sum++;
	if(ch[i]>='5') ch[i-1]++;
	for(int j=0;j<i;j++) printf("%c",ch[j]);
}
void work()
{
	while(SPFA()) dfs();
	//cout<<ans<<endl;
	if(ans>zero) print(ans);
	else printf("0");
}
int main()
{
	freopen("agent.in","r",stdin);
	freopen("agent.out","w",stdout);
	read();
	work();
	return 0;
}