题意:给n个点，每个点上有x个人和y份食物，给m条边，每条边有走断的概率，不过第一次走是不会断的，点上的人可以通过边来移动，问你让所有人吃上饭破坏边的最小概率
思路：求破坏边的最小概率可以转换成不破坏边的最大概率，考虑到精度问题，我们通过对数运算把乘法转换成加法，设置一个超级源点和一个超级汇点，然后跑一遍最小费用最大流即可，注意使用eps精度修正
代码:
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f const double eps= 1e-8; const int maxn=2e2+9; struct Point { int x,y;//x代表人,y代表食物 }a[maxn]; struct node{ int to,next,cap; double cost; }edge[20009]; int s,t,n,cnt=0,vis[maxn],head[maxn],pre_id[maxn],pre_pt[maxn]; double dis[maxn]; double sum; void add(int u,int v ,int cap,double cost){ edge[cnt].next=head[u]; edge[cnt].to=v; edge[cnt].cap=cap; edge[cnt].cost=cost; head[u]=cnt++; } bool spfa(int s,int t){ //cout<<n<<endl; for(int i=1;i<=n+1;i++){ dis[i]=inf; } dis[s]=0.0;vis[s]=1; queue<int>q;q.push(s); while(!q.empty()){ int u=q.front(); q.pop();vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(edge[i].cap&&dis[v] >dis[u]+edge[i].cost+eps){ dis[v]=edge[i].cost+dis[u]; pre_pt[v]=u; pre_id[v]=i; if(vis[v])continue; q.push(v); vis[v]=1; } } } if(dis[t]==inf)return false; return true; } void EK(){ while(spfa(s,t)){ int Min=inf; for(int i=t;i!=s;i=pre_pt[i]){ Min=min(Min,edge[pre_id[i]].cap); } for(int i=t;i!=s;i=pre_pt[i]){ edge[pre_id[i]].cap-=Min; edge[pre_id[i]^1].cap+=Min; } sum+=(double)Min*dis[t]; } } int main(){ int i,j,k,m,tim; scanf("%d",&tim); while(tim--){ cnt=0,sum=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d%d",&a[i].x,&a[i].y); } for(i=0;i<m;i++){ int x,y,c;double p; scanf("%d%d%d%lf",&x,&y,&c,&p); p=-log2(1-p); if(c>0){ add(x,y,1,0); add(y,x,0,0); } if(c-1>0){ add(x,y,c-1,p); add(y,x,0,-p); } } s=0,t=n+1; for(i=1;i<=n;i++){ if(a[i].x-a[i].y>0){ add(s,i,a[i].x-a[i].y,0); add(i,s,0,0); } else{ add(i,t,a[i].y-a[i].x,0); add(t,i,0,0); } } EK(); //cout<<sum<<endl; double ans=1-pow(2,-sum); printf("%.2f\n",ans); } }
