# POJ3308[Paratroopers]

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-21

DESCRIPTION:

http://acm.pku.edu.cn/JudgeOnline/problem?id=3308

*/

#include <stdio.h>

#include <string.h>

#include <math.h>

const double oo=1e10;

const double zero=1e-10;

const int MAXV=1000000;

const int MAXE=1000000;

typedef struct struct_edge* edge;

struct struct_edge{int v;double c;edge n,b;};

struct_edge pool[MAXE];

edge top;

int S,T,V;

int d[MAXV];

int q[MAXV];

{

}

bool is_zero(double a)

{

return fabs(a)<=zero;

}

bool relabel()

{

for (int i=0;i<V;d[i++]=V) ;

{

if (!is_zero(i->b->c)&&d[i->v]==V)

d[q[++tail]=i->v]=d[u]+1;

if (d[S]!=V) return true;

}

return false;

}

double augment(int u,double e)

{

if (u==T) return e;

double f=0;

if (!is_zero(i->c)&&d[u]==d[i->v]+1)

{

double df=augment(i->v,e<i->c?e:i->c);

i->c-=df,i->b->c+=df,e-=df,f+=df;

}

return f;

}

double dinic()

{

double f=0;

while (relabel()) f+=augment(S,oo);

return f;

}

int t;

int m,n,l;

int main()

{

scanf(“%d”,&t);

for (int tt=0;tt<t;tt++)

{

scanf(“%d%d%d”,&m,&n,&l);

top=pool;

S=0,T=m+n+1,V=m+n+2;

for (int i=1;i<=m;i++)

{

double a;

scanf(“%lf”,&a);

}

for (int i=1;i<=n;i++)

{

double a;

scanf(“%lf”,&a);

}

for (int i=0;i<l;i++)

{

int a,b;

scanf(“%d%d”,&a,&b);

}

printf(“%.4f\n”,double(exp(dinic())));

}

}