记录编号	367644	评测结果	AAAAAAAAAAAAAA
题目名称	[CTSC 2001]终极情报网	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2017-01-31 22:10:16	内存使用	6.51 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
typedef double db;
const db eps=1e-12;
const int N=1e5+10;
struct edge{int f,t,g,o;db l;}w[N];
int n,k,s,t,cnt,head[N],tail[N],next[N];
db as[N];int am[N];
void add(int f,int t,int g,db l){
	++cnt;w[cnt]=(edge){f,t,g,cnt+1,l};
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
	++cnt;w[cnt]=(edge){t,f,0,cnt-1,1/l};
	if (!head[t]) head[t]=tail[t]=cnt;
		else tail[t]=next[tail[t]]=cnt;
}
db dis[N],ans;int from[N],flow[N],Flow;
bool inque[N];
queue<int> Q;
bool spfa(){
	for (int i=s;i<=t;i++) dis[i]=0;
	dis[s]=1;flow[s]=1e9;Q.push(s);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		inque[v]=0;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&dis[w[i].t]+eps<dis[v]*w[i].l){
			int u=w[i].t;
			dis[u]=dis[v]*w[i].l;
			from[u]=i;
			flow[u]=min(flow[v],w[i].g);
			if (!inque[u]) inque[u]=1,Q.push(u);
		}
	}
	if (dis[t]<eps) return 0;
	int df=flow[t];
	Flow+=df;ans*=pow(dis[t],df);
	for (int i=from[t];i;i=from[w[i].f])
		w[i].g-=df,w[w[i].o].g+=df;
	return 1;
}
void print(db ans){
	int bit=-floor(log(ans)/log(10))+4;
	char s[10]="%.";int len=0;
	sprintf(s+2,"%d",bit);
	while (s[len]) len++;
	sprintf(s+len,"lf\n");
	//puts(s);
	printf(s,ans);
}
int main()
{
	freopen("agent.in","r",stdin);
	freopen("agent.out","w",stdout);
	scanf("%d%d",&n,&k);
	s=0;t=n+2;
	add(n+1,t,k,1);
	for (int i=1;i<=n;i++) scanf("%lf",&as[i]);
	for (int i=1;i<=n;i++){
		scanf("%d",&am[i]);
		if (am[i]) add(s,i,am[i],as[i]);
	}
	for (int i=1,x;i<=n;i++){
		scanf("%d",&x);
		if (x) add(i,n+1,1e9,1);
	}
	while (1){
		int f,t,g;db l;
		scanf("%d%d",&f,&t);
		if (f==-1&&t==-1) break;
		scanf("%lf%d",&l,&g);
		add(f,t,g,l);
		add(t,f,g,l);
	}
	ans=1;while (spfa());
	if (Flow!=k||ans<eps) puts("0.0000"),exit(0);
	print(ans);
	return 0;
}