列表

详情

NC19030. Coding Contest

描述

A coding contest will be held in this university, in a huge playground. The whole playground would be divided into N blocks, and there would be M directed paths linking these blocks. The i-th path goes from the ui-th block to the vi-th block. Your task is to solve the lunch issue. According to the arrangement, there are si competitors in the i-th block. Limited to the size of table, bi bags of lunch including breads, sausages and milk would be put in the i-th block. As a result, some competitors need to move to another block to access lunch. However, the playground is temporary, as a result there would be so many wires on the path. 
For the i-th path, the wires have been stabilized at first and the first competitor who walker through it would not break the wires. Since then, however, when a person go through the i−th path, there is a chance of pi to touch the wires and affect the whole networks. Moreover, to protect these wires, no more than ci competitors are allowed to walk through the i-th path. 
Now you need to find a way for all competitors to get their lunch, and minimize the possibility of network crashing. 

输入描述

The first line of input contains an integer t which is the number of test cases. Then t test cases follow. 
For each test case, the first line consists of two integers N (N ≤ 100) and M (M ≤ 5000). Each of the next N lines contains two integers si and bi (si,bi ≤ 200). 
Each of the next M lines contains three integers ui,vi and ci(ci ≤ 100) and a float-point number pi(0 < pi < 1). It is guaranteed that there is at least one way to let every competitor has lunch. 

输出描述

For each turn of each case, output the minimum possibility that the networks would break down. Round it to 2 digits.

示例1

输入: 

1
4 4
2 0
0 3
3 0
0 3
1 2 5 0.5
3 2 5 0.5
1 4 5 0.5
3 4 5 0.5

输出: 

0.50

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 660ms, 内存消耗: 852K, 提交时间: 2018-10-07 15:23:11 

#include<bits/stdc++.h>
using namespace std;const int N=2e4+7;const double eps=1e-8,inf=-1e60;
struct data{int to,next,v,from;double c;}e[N*10];int head[N],from[N],inq[N],cnt=1,S,T,T_T,t,w,x,n,m,i,j,q[N];double d[N],ans,p;
void ins(int u,int v,int w,double c)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;e[cnt].c=c;e[cnt].from=u;}
void insert(int u,int v,int w,double c){ins(u,v,w,c);ins(v,u,0,-c);}
bool spfa(){
    for(i=0;i<=T;++i)d[i]=inf;d[0]=S;inq[S]=1;q[0]=S;t=0;w=1;
    while(t!=w){
        x=q[t++];if(t==N)t=0;inq[x]=0;
        for(i=head[x];i;i=e[i].next)if(e[i].v&&d[e[i].to]+eps<d[x]+e[i].c){
            d[e[i].to]=d[x]+e[i].c;
            from[e[i].to]=i;
            if(!inq[e[i].to]){inq[e[i].to]=1;q[w++]=e[i].to;if(w==N)w=0;}
        }
    }return fabs(d[T]-inf)>eps;
}
void mincf(){
    x=1e9;for(i=from[T];i;i=from[e[i].from])x=min(x,e[i].v);
    for(i=from[T];i;i=from[e[i].from])e[i].v-=x,e[i^1].v+=x,ans+=x*e[i].c;
}
int main(){
    for(scanf("%d",&T_T);T_T--;memset(head,0,sizeof(head)),ans=0,cnt=1){
        for(scanf("%d%d",&n,&m),S=0,T=n+1,x=1;x<=n;++x){
            scanf("%d%d",&i,&j);
            if(i-j>0)insert(S,x,i-j,0);
            else if(i-j<0)insert(x,T,j-i,0);
        }
        for(;m--;){
            scanf("%d%d%d%lf",&i,&j,&x,&p);p=1-p;
            if(x>0)insert(i,j,1,0);
            if(x>1)insert(i,j,x-1,log(p));
        }while(spfa())mincf();printf("%.2f\n",1-exp(ans));
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 691ms, 内存消耗: 960K, 提交时间: 2020-02-27 21:42:15 

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+7;
const double eps=1e-8,inf=-1e60;
struct data
{
	int to,next,v,from;
	double c;
}e[N*10];
int head[N],from[N],inq[N],cnt=1,S,T,T_T,t,w,x,n,m,i,j,q[N];
double d[N],ans,p;
void ins(int u,int v,int w,double c)
{
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
	e[cnt].v=w;
	e[cnt].c=c;
	e[cnt].from=u;
}
void insert(int  u,int v,int w,double c)
{
	ins(u,v,w,c);
	ins(v,u,0,-c);
}
bool spfa()
{
	for(i=0;i<=T;++i)
	d[i]=inf;
	d[0]=S;
	inq[S]=1;
	q[0]=S;
	t=0;
	w=1;
	while(t!=w)
	{
		x=q[t++];
		if(t==N) t=0;
		inq[x]=0;
		for(i=head[x];i;i=e[i].next)
		if(e[i].v&&d[e[i].to]+eps<d[x]+e[i].c)
		{
			d[e[i].to]=d[x]+e[i].c;
			from[e[i].to]=i;
			if(!inq[e[i].to])
			{
				inq[e[i].to]=1;
				q[w++]=e[i].to;
				if(w==N) w=0; 
			}
		}
	}
	return fabs(d[T]-inf)>eps;
}
void mincf()
{
	x=1e9;
	for(i=from[T];i;i=from[e[i].from])
	x=min(x,e[i].v);
	for(i=from[T];i;i=from[e[i].from])
	e[i].v-=x,e[i^1].v+=x,ans+=x*e[i].c;
}
int main()
{
	for(scanf("%d",&T_T);T_T--;memset(head,0,sizeof(head)),ans=0,cnt=1)
	{
		for(scanf("%d%d",&n,&m),S=0,T=n+1,x=1;x<=n;++x)
		{
			scanf("%d%d",&i,&j);
			if(i-j>0) insert(S,x,i-j,0);
			else if(i-j<0) insert(x,T,j-i,0);
		}
		for(;m--;)
		{
			scanf("%d%d%d%lf",&i,&j,&x,&p);
			p=1-p;
			if(x>0) insert(i,j,1,0);
			if(x>1) insert(i,j,x-1,log(p));
		}
		while(spfa())
		mincf();
		printf("%.2f\n",1-exp(ans));
	}
}

上一题

© 2025 nowcoder.com