Hefei 2015

Bus Routes

Advanced Calculator

Autopilot System

lbn187

#include<bits/stdc++.h>
#define N 20200
#define M 205
#define eps 1e-8
#define CL(a) memset(a,0,sizeof a)
int ca,T,n,m,i,j,k,x,y,tot,fir[N],ne[N*2],la[N*2],u[M],du[N];
double V,an,o,v[M],F[N],G[N],H[N],a[M][M];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[y]++;}
void cl(){for(int i=1;i<=n;i++)F[i]=G[i]=H[i]=0.0;}
bool dfs(int x,int fa){
	int i,y;double o=1.0,w=(1.0-V)/du[x];
	F[x]=w;G[x]=1.0;H[x]=1.0-V;
	for(i=fir[x];i;i=ne[i]){
		y=la[i];
		if(y!=fa){
			if(!dfs(y,x))assert(0);
			G[x]+=w*G[y];H[x]+=w*H[y];o-=w*F[y];
		}
	}
	if(x==n){
		F[x]=G[x]=H[x]=0.0;
		return 1;
	}
	if(fabs(o)<eps)return 0;
	F[x]/=o;G[x]/=o;H[x]/=o;
	return 1;
}
int main(){
	scanf("%d",&T);
	for(ca=1;ca<=T;ca++,puts("")){
		CL(fir);CL(du);tot=0;V=0.0;
		scanf("%d%d",&n,&m);
		for(i=1;i<=m;i++)scanf("%d%lf",&u[i],&v[i]),V+=v[i];
		for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
		printf("Case #%d: ",ca);
		if(fabs(1.0-V)<eps){
			bool ff=0;
			for(i=1;i<=m;i++)if(u[i]==n&&v[i]>eps)ff=1;
			if(ff)puts("0.000000");else puts("impossible");
			continue;
		}
		for(i=1;i<=m;i++)for(j=1;j<=m+1;j++)a[i][j]=0.0;
		for(i=1;i<=m;i++){
			cl();x=u[i];dfs(x,0);
			a[i][i]=1.0;
			for(j=1;j<=m+1;j++)a[i][j]-=v[j]*G[x];
			a[i][m+1]=H[x];
		}
		for(i=1;i<=m;i++){
			o=a[i][i];
			if(fabs(o)<eps)continue;
			for(j=1;j<=m+1;j++)a[i][j]/=o;
			for(j=1;j<=m;j++)if(i!=j)
				for(o=a[j][i],k=1;k<=m+1;k++)
					a[j][k]-=o*a[i][k];
		}
		cl();dfs(1,0);an=H[1];
		for(i=1;i<=m;i++)an+=G[1]*v[i]*a[i][m+1];
		printf("%.9f\n",an);
	}
}

Kingdom of Tree