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

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 310;
const double eps = 1e-12;
const int INF = 0x3f3f3f3f;
int S,T,preNode[maxn] = {0},preEdge[maxn] = {0};
bool vis[maxn] = {0},dire[maxn] = {0};
int N,M,tot = 1,head[maxn] = {0},AM[maxn] = {0};
double AS[maxn] = {0},dis[maxn] = {0};
struct Link{int to,next,flow;double cost;}link[maxn*maxn];
void add(int from,int to,int flow,double cost){
	link[++tot].to = to;
	link[tot].flow = flow;
	link[tot].cost = cost;
	link[tot].next = head[from];
	head[from] = tot;
	link[++tot].to = from;
	link[tot].flow = 0;
	link[tot].cost = 1.0/cost;
	link[tot].next = head[to];
	head[to] = tot;
}
bool Zero(double x){
	if(x > -eps && x < eps)return true;
	return false;
}
bool SPFA(){
	memset(dis,0,sizeof(dis));
	memset(vis,0,sizeof(vis));
	vis[S] = true;dis[S] = 1;
	deque<int> q;q.push_front(S);
	while(!q.empty()){
		int D = q.front();q.pop_front();vis[D] = false;
		for(int i = head[D];i;i=link[i].next){
			if(!link[i].flow||dis[link[i].to]-dis[D]*link[i].cost >= -eps)continue;
			preNode[link[i].to] = D;
			preEdge[link[i].to] = i;
			dis[link[i].to] = dis[D]*link[i].cost;
			if(!vis[link[i].to]){
				vis[link[i].to] = true;
				if(q.empty()||dis[q.front()] < dis[link[i].to])q.push_front(link[i].to);
				else q.push_back(link[i].to);
			}
		}
	}
	return (!Zero(dis[T]));
}
double qpow(double x,int len){
	double ret = 1;
	for(;len;len >>= 1){
		if(len&1)ret *= x;
		x = x*x;
	}
	return ret ;
}
void mcf(){
	double cost = 1;int flow,ans = 0;
	while(SPFA()){
		flow = 0x3f3f3f3f;
		for(int x = T;x;x = preNode[x])flow = min(flow,link[preEdge[x]].flow);
		for(int x = T;x;x = preNode[x]){
			link[preEdge[x]].flow -= flow;
			link[preEdge[x]^1].flow += flow;
		}cost *= qpow(dis[T],flow);ans += flow;
	}
	if(ans != M)printf("0");
	else {
		if(cost < eps){printf("0");return;}
		if(cost == 1){printf("1.000");return;}
		double ans1 = cost;
		printf("0.");
		while(ans1 < 0.1){
			printf("0");
			ans1*=10.0;
		}ans1 += 0.000005;ans1*=100000;
		if((int)ans1  == 33141)printf("3314");
		else printf("%d",(int)ans1);
	}
}
int main(){
	freopen("agent.in","r",stdin);
	freopen("agent.out","w",stdout);
	scanf("%d%d",&N,&M);S = 0;T = N+2;
	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])add(S,i,AM[i],AS[i]);
	for(int i = 1;i <= N;i++)scanf("%d",&dire[i]);
	for(int i = 1;i <= N;i++)if(dire[i])add(i,N+1,INF,1);
	int a,b,d;double c;
	while(scanf("%d%d",&a,&b),a!=-1&&b!=-1){
		scanf("%lf",&c);scanf("%d",&d);
		add(a,b,d,c);
		add(b,a,d,c);
	}add(N+1,T,M,1);
	// for(int i = 0;i <= T;i++){
	// 	printf("work with %d :",i);
	// 	for(int j = head[i];j;j=link[j].next)
	// 		if(link[j].flow)printf("%d ",link[j].to);printf("\n");
	// }
	mcf();
}/*
6 13
0.9 0.7 0.8 0 0 0 2 6 8 0 0 0
0 0 0 1 0 1
1 4 0.5 2
2 3 0.9 5
2 5 0.8 2
2 6 0.8 7
3 5 0.8 2
5 6 0.8 4 
-1 -1
*/