1 /*************************************************************************
  2     > File Name: coding_contest.cpp
  3     > Author: CruelKing
  4     > Mail: [email?protected] 
  5     > Created Time: 2019年09月18日 星期三 10时15分58秒
  6     本题思路:    本题要求使得所有人都找到吃饭的地方且使得网络被破坏的可能性最小,因此
  7     很简单可以看出来是个费用流,但是费用流一般都是统计增广路上的花费的和最小而这里我们
  8     要求的概率为p1 * p2 * p.... * pn最小,因此我们可以想到,可以用对要算的式子取对数就很
  9     容易可以将乘法转换为加法,即我们计算ln(p1) + ln(p2) + ... + ln(pn)然后对结果再取
 10     e的指数(刚算的结果作为指数)很容易就可以求得正解,但是这里我们发现由于我们取得log
 11     底数为e,且概率都是小于1的,因此我们得到费用的值都为负数,这样统计我们得到的是费用
 12     的最大值也即概率的最大值就有错误,所以此时我们可以将问题转换为求解网络不被破坏的
 13     可能行最大的问题,也就是使得(1 - p1) * (1 - p2) * ....* (1 - pn)最大,很容易我们
 14     又可以将其转为log,得到ln(1 - p1) + ln(1 - p2) + ... + ln(1 - pn)最大,同样我们又
 15     可以得到一堆负值,所以我们可以将问题转化非求解原问题的倒数最小的问题,那么很容易
 16     我们就可以得到使得-(ln(1 - p1) + ln(1 - p2) + ... + ln(1 - pn))最小即可,也就是说
 17     我们可以将边的花费设置为 - ln(1 - pi)然后跑费用流就可以了,具体如何建图呢?
 18     我们知道每个结点初始情况可能下有人,而且每个结点还有一个上限,我们首先建立超级源点
 19     s和超级汇点t,对于初始情况下的结点,如果一个结点的s[i] - b[i] > 0那么我们就从s到i
 20     建一条容量为s[i] - b[i]的边,花费为0,如果s[i] - b[i] < 0我们就建一条从i到t的边, 21     容量为b[i] - s[i],又由于第一次踩一根线网络不可能出问题,那我们就拆边,把
 22     原来的边拆为一条容量为1花费为0,另一条容量为c[i] - 1花费为-log(1 - p[i])的边.
 23     ok跑一波费用流.
 24  ************************************************************************/
 25 
 26 #include <cstdio>
 27 #include <cstring>
 28 #include <cmath>
 29 #include <queue>
 30 #include <algorithm>
 31 using namespace std;
 32 
 33 const int maxn = 100 + 5,maxm = 5000 + 5,inf = 0x3f3f3f3f;
 34 int n,m,s,t;
 35 
 36 const double eps = 1e-8;
 37 int head[maxn],tot;
 38 
 39 struct Edge {
 40     int to,flow,cap,next;
 41     double cost;
 42 } edge[maxm << 2];
 43 
 44 void init() {
 45     memset(head,-1,sizeof head);
 46     tot = 2;
 47 }
 48 
 49 void addedge(int u,int v,int cap,double cost) {
 50     edge[tot].to = v; edge[tot].flow = 0; edge[tot].cap = cap; edge[tot].cost = cost;
 51     edge[tot].next = head[u]; head[u] = tot ++;
 52     edge[tot].to = u; edge[tot].flow = 0; edge[tot].cap = 0; edge[tot].cost = -cost;
 53     edge[tot].next = head[v]; head[v] = tot ++;
 54 }
 55 
 56 int pre[maxn];
 57 double dis[maxn];
 58 bool vis[maxn];
 59 int cnt[maxn];
 60 
 61 bool spfa() {
 62     queue<int> que;
 63     for(int i = 0; i <= n + 2; i ++) {
 64         dis[i] = inf;
 65         vis[i] = false;
 66         pre[i] = -1;
 67         cnt[i] = 0;
 68     }
 69     cnt[s] = 1;
 70     dis[s] = 0.0;
 71     vis[s] = true;
 72     que.push(s);
 73     while(!que.empty()) {
 74         int u = que.front();    que.pop();    vis[u] = false;
 75         for(int i = head[u]; ~i; i = edge[i].next) {
 76             int v = edge[i].to;
 77             if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost + eps) {
 78                 dis[v] = dis[u] + edge[i].cost;
 79                 pre[v] = i;
 80                 if(!vis[v]) {
 81                     cnt[v] ++;
 82                     vis[v] = true;
 83                     que.push(v);
 84                     if(cnt[v] > n) return false;
 85                 }
 86             }
 87         }
 88     }
 89     if(pre[t] == -1) return false;
 90     else return true;
 91 }
 92 
 93 void mincostmxflow (double &ans) {
 94     while(spfa()) {
 95         int Min = inf;
 96         for(int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
 97             if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow;
 98         }
 99         for(int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
100             edge[i].flow += Min;
101             edge[i ^ 1].flow -= Min;
102             ans += edge[i].cost * Min;
103         }
104     }
105 }
106 
107 int main() {
108     int _case,si,bi,u,v,c;
109     double pi;
110     scanf("%d",&_case);
111     while(_case --) {
112         init();
113         scanf("%d %d",&n,&m);
114         s = 0,t = n + 1;
115         for(int i = 1; i <= n; i ++) {
116             scanf("%d %d",&si,&bi);
117             if(si > bi) addedge(s,i,si - bi,0.0);
118             else if(si < bi) addedge(i,t,bi - si,0.0);
119         }
120         for(int i = 0; i < m; i ++) {
121             scanf("%d %d %d %lf",&u,&v,&c,&pi);
122             if(c > 0) addedge(u,1,0.0);
123             if(c > 1) addedge(u,c - 1,-log2(1 - pi));
124         }
125         double ans = 0;
126         mincostmxflow(ans);
127         printf("%.2fn",1.0 - pow(2,-ans));
128     }
129     return 0;
130 }