很巧妙的建边方式
题意：有n个区域，每个区域有一些人数si和食物bi，区域之间有m条定向路径，每条路径有人数通过上限ci。路径之间铺了电线，每当有人通过路径时有pi的概率会触碰到电线，但是第一个通过的人一定不会触碰到电线。求每个人都通过路径获取到食物后触碰到电线的最小概率。
解法：不碰到电线的概率比较好求，然后对于一条路线上的不碰到电线的概率是(1-p1)*(1-p2)...，最小费用流是没法跑乘法的，所以我们建边的费用变成log(1-p)，那么乘法就变成了加法，然后要求最小值，由于log(1-p)小于0，所以我们取-log（1-p），然后跑完最小费用流后exp（-ans）就是答案了，对于第一个人是没有概率的，那么我们把大于1的边拆成两条边，其中一条流量为1，费用为0即可
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define vi vector<int> #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pli pair<ll,int> #define pii pair<int,int> #define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-8; const int N=10000+10,maxn=100000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; struct edge{ int to,Next,c; double cost; }e[maxn]; int cnt,head[N]; int s,t; int pre[N],path[N]; double dis[N]; bool vis[N]; void add(int u,int v,int c,double cost) { e[cnt].to=v; e[cnt].c=c; e[cnt].cost=cost; e[cnt].Next=head[u]; head[u]=cnt++; e[cnt].to=u; e[cnt].c=0; e[cnt].cost=-cost; e[cnt].Next=head[v]; head[v]=cnt++; } bool spfa() { memset(pre,-1,sizeof pre); for(int i=0;i<N;i++)dis[i]=2e9; memset(vis,0,sizeof vis); dis[s]=0; vis[s]=1; queue<int>q; q.push(s); while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=head[x];~i;i=e[i].Next) { int te=e[i].to; if(e[i].c>0&&dis[x]+e[i].cost+eps<dis[te]) { dis[te]=dis[x]+e[i].cost; pre[te]=x; path[te]=i; if(!vis[te])q.push(te),vis[te]=1; } } } return pre[t]!=-1; } double mincostmaxflow() { int flow=0; double cost=0.0; while(spfa()) { int f=inf,ok=0; for(int i=t;i!=s;i=pre[i]) if(e[path[i]].c<f) f=e[path[i]].c; flow+=f; cost+=(dis[t])*f; for(int i=t;i!=s;i=pre[i]) { e[path[i]].c-=f; e[path[i]^1].c+=f; } } return cost; } void init() { memset(head,-1,sizeof head); cnt=0; } int main() { int T;scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); s=n+1,t=n+2; init(); for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); x-=y; if(x>0)add(s,i,x,0); else if(x<0)add(i,t,-x,0); } for(int i=1;i<=m;i++) { int u,v,c;double p; scanf("%d%d%d%lf",&u,&v,&c,&p); if(c>0)add(u,v,1,0); if(c-1>0)add(u,v,c-1,-log(1-p)); } printf("%.2f ",1-exp(-mincostmaxflow())); } return 0; } /*********************** 1 4 4 2 0 0 3 3 0 0 3 1 2 5 0.5 3 2 5 0.5 1 4 5 0.5 3 4 5 0.5 ***********************/