题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5988

题意：n个点有人有面包，有一些边，除了第一个走这个边的人其他人都有pi的概率破坏网络，让你安排吃饭

方案，使得每个人吃上饭，并且破坏网络的概率最小。

解法：这是2016青岛赛区的银牌题，当时并不会做，今年学了一些网络流决心来A掉这个题。所以就有了下面

的的惨剧。

来说说做法吧，其实并不难。不过这里面相当于有一个拆边的思想。

破坏网络概率最小就是不破坏网络概率最大，那么就是一个乘积最大的表达式，加一个log就变成了加法，典

型的费用流问题。建边也很简单，源点连向人多余的，吃的多余的点连向汇点，中间建边记得拆边，因为第一

个人不要费用。。剩下的就是愉快的费用流一下。

坑点：double 的费用流如果你要写spfa的最短路里面有浮点数的比较大小，如果不加eps的修正会

tle。。。。

我T了10次就是没考虑到这个。

//HDU 5988

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-7;
const double inf = 2e9;
const int maxn = 205;
const int maxm = 50010;

struct node{
    int st, en, next, flow;
    double cost;
    node(){}
    node(int st, int en, int next, int flow, double cost):st(st),en(en),next(next),flow(flow),cost(cost){}
}E[maxm];

int p[maxn], num;

void init(){
    num = 0;
    memset(p, -1, sizeof(p));
}

void add(int st, int en, int flow, double cost){
    E[num] = node(st,en,p[st],flow,cost); p[st] = num++;
    E[num] = node(en,st,p[en],0,-cost); p[en] = num++;
}

int pre[maxn];
double dis[maxn];
bool fg[maxn];

bool spfa(int st, int en){
    for(int i=0; i<=en; i++) fg[i]=0, dis[i]=inf, pre[i]=-1;
    queue <int> q;
    q.push(st);
    fg[st]=1;
    dis[st]=0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        fg[u]=0;
        for(int i=p[u]; i+1; i=E[i].next){
            int v=E[i].en;
            if(E[i].flow&&dis[v]-dis[u]-E[i].cost>eps){
                dis[v]=dis[u]+E[i].cost;
                pre[v]=i;
                if(!fg[v]){
                    fg[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(pre[en]==-1) return 0;
    else return 1;
// if(dis[en]+eps<inf) return 1;
// else return 0;
}

double solve(int st, int en)
{
    double ans=0;
    while(spfa(st, en)){
        int d = 0x3f3f3f3f;
        for(int i=pre[en]; i+1; i=pre[E[i].st]) d = min(d, E[i].flow);
        for(int i=pre[en]; i+1; i=pre[E[i].st]){
            E[i].flow-=d;
            E[i^1].flow+=d;
            ans += 1.0*d*E[i].cost;
        }
    }
    return ans;
}

int main()
{
    int t; scanf("%d", &t);
    while(t--){
        int n, m;
        scanf("%d%d", &n, &m);
        init();
        for(int i=1; i<=n; i++){
            int s, b;
            scanf("%d%d", &s, &b);
            int f = s-b;
            if(f>0) add(0, i, f, 0);
            else if(f<0) add(i, n+1, -f, 0);
        }
        while(m--){
            int u,v,f;
            double w;
            scanf("%d%d%d%lf", &u,&v,&f,&w);
            w = -log2(1.0-w);
            if(f>0) add(u,v,1,0.0);
            if(f-1>0) add(u,v,f-1,w);
        }
        double ans = solve(0,n+1);
        ans = 1.0-pow(2.0,-ans);
        printf("%.2f\n", ans);
    }
    return 0;
}