费用不再是相加，而是以概率形式出现，需要相乘

取对数可以将乘法变为加法

然后就是裸的费用流了

注意精度问题，不然会T。。。

---

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define INF 0x3f3f3f3f#define eps 1e-8using namespace std;typedef long long LL;typedef pair
          
            P;const int maxv = 1e2 + 10;int V;struct edge { int to, cap, rev; double cost; edge(int to, int cap, double cost, int rev) : to(to), cap(cap), cost(cost), rev(rev) {}};double h[maxv];double dist[maxv];int prevv[maxv], preve[maxv];vector
           
             G[maxv];void add_edge(int from, int to, int cap, double cost) { G[from].push_back(edge(to, cap, cost, G[to].size())); G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));}double min_cost_flow(int s, int t, int f) { double res = 0; for (int i = 0; i <=V; i++) h[i] = 0; while (f > 0) { priority_queue
            
             , greater
             
 > que; for (int i = 0; i < V; i++) dist[i] = 1e18; dist[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (dist[v] < p.first) continue; for (int i = 0; i < G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && dist[e.to] - dist[v] - e.cost - h[v] + h[e.to] > eps) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; que.push(P(dist[e.to], e.to)); } } } for (int v = 0; v < V; v++) h[v] += dist[v]; int d = f; for (int v = t; v != s; v = prevv[v]) { d = min(d, G[prevv[v]][preve[v]].cap); } res += d * h[t]; f -= d; for (int v = t; v != s; v = prevv[v]) { edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res;}int main() { int Te; scanf("%d", &Te); while (Te--) { int f = 0; int N, M; int S, T; scanf("%d%d", &N, &M); S = 0; T = N + 1; V = T + 1; for (int i = 0; i < V; i++) G[i].clear(); int u, v, c; double p; for (int i = 1; i <= N; i++) { scanf("%d%d", &u, &v); if (u > v) { f += (u - v); add_edge(S, i, u - v, 0); } else if (u < v) { add_edge(i, T, v - u, 0); } } for (int i = 0; i < M; i++) { scanf("%d%d%d%lf", &u, &v, &c, &p); p = -log2(1 - p); if (c > 0) { add_edge(u, v, 1, 0); add_edge(u, v, c - 1, p); } } double ans = min_cost_flow(S, T, f); printf("%.2lf\n", 1.000 - pow(2, -ans)); } return 0;}