记录编号	92156	评测结果	AAAAAAAAAAAAAA
题目名称	[CTSC 2001]终极情报网	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2014-03-18 22:02:51	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iomanip>
#include<cmath>
#include<cstdlib>
using namespace std;
const int SIZEN=500,INF=0x7fffffff;
const double eps=1e-12;
class EDGE{
public:
	int from,to,cap,flow;
	double cost;
};
vector<EDGE> edges;
vector<int> c[SIZEN];
int N;//从0到N
int S,T;
int K;//传递消息数
void addedge(int from,int to,int cap,double cost){
	edges.push_back((EDGE){from,to,cap,0,cost});
	edges.push_back((EDGE){to,from,0,0,1.0/cost});//反悔边的权值得按乘法的特性来
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
double anscost=1.0;
int ansflow=0;
bool SPFA(int S,int T){
	queue<int> Q;
	double dist[SIZEN]={0};//最大可靠度
	bool inq[SIZEN]={0};
	int father[SIZEN]={0};
	dist[S]=1,inq[S]=true,Q.push(S);
	while(!Q.empty()){
		int u=Q.front();inq[u]=false;Q.pop();
		for(int i=0;i<c[u].size();i++){
			EDGE &now=edges[c[u][i]];
			if(now.cap<=now.flow) continue;
			if(dist[now.to]+eps<dist[u]*now.cost){
				dist[now.to]=dist[u]*now.cost;
				father[now.to]=c[u][i];
				if(!inq[now.to]){
					inq[now.to]=true;
					Q.push(now.to);
				}
			}
		}
	}
	if(dist[T]<eps) return false;
	int nowf=INF,x=T;
	while(x!=S){
		EDGE &now=edges[father[x]];
		nowf=min(nowf,now.cap-now.flow);
		x=now.from;
	}
	ansflow+=nowf;
	anscost*=pow(dist[T],nowf+0.0);//nowf件物品的可靠度乘起来
	x=T;
	while(x!=S){
		edges[father[x]].flow+=nowf;
		edges[father[x]^1].flow-=nowf;
		x=edges[father[x]].from;
	}
	return true;
}
int AM[SIZEN]={0};//和总部传递的信息数量
double AS[SIZEN]={0};//和总部联系的安全程度
bool ges[SIZEN]={0};//是否和德军情报部联系
void print15(double ans){
	char ch[40]={0};
	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]++;
	ch[i]=0;
	for(;i>=0;i--){
		if(ch[i]=='.') break;
		if(ch[i]>'9') ch[i-1]++,ch[i]='0';
	}
	printf("%s\n",ch);
}
void work(void){
	while(SPFA(S,T));
	if(ansflow<K||anscost<eps){
		printf("0\n");
		return;
	}
	print15(anscost);
}
void makegraph(void){
	scanf("%d%d",&N,&K);
	S=0,T=N+1;
	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]) addedge(S,i,AM[i],AS[i]);
	for(int i=1;i<=N;i++) scanf("%d",&ges[i]);
	for(int i=1;i<=N;i++) if(ges[i]) addedge(i,T,K,1.0);
	int a,b,m;
	double s;
	while(true){
		scanf("%d%d",&a,&b);
		if(a==-1&&b==-1) break;
		scanf("%lf%d",&s,&m);
		addedge(a,b,m,s);
		addedge(b,a,m,s);
	}
	addedge(N+2,S,K,1);
	S=N+2;
	N+=2;
}
int main(){
	freopen("agent.in","r",stdin);
	freopen("agent.out","w",stdout);
	makegraph();
	work();
	return 0;
}