题意：一个网络流的图，有n个点，从1~n，然后m条边，每个点有两个值，一个是人的数量si一个是饭的数量bi。每条m边有容量ci，还有走上去可能踩断电线的概率pi(第一次踩上去没有事，之后都要p概率)。问让所有人吃到饭的前提下断电线的最小概率是多少。
解法：每条边有走的次数（流量），每条边走一次发生破坏概率为p（流量1，费用p），容易想到费用流。可是费用流往往是费用相加的，这个是概率，只能相乘。有什么办法，log函数可以把乘除法转换为加减法。所以对每个概率取个log当成费用就行了。
注意，这个概率是踩坏的概率，你数学思维一下，求总的踩坏概率不可能会是说全部都是踩坏的概率相乘吧，我也可以有一些边是可以吧被拆坏，所以我们需要求对立面
这时候就应该从反方向进行考虑，求踩坏的最小概率，就是求不踩坏的最大概率，1-p后取log，和以上同理，求出了最大费用。取出来还回去后用1减一下就好了。
新建源点s，汇点t，对于S>B的需要人走，从源点连一条流量为S[i]-B[i]，费用为0(出门不需要费用)的边过去，add(s,i,S[i]-B[i],0)，对于s<b的，add(i,t,B[i]-S[i],0)。
为什么要这样建边呢，是因为从源点s出来的人要到汇点t去，到汇点的边就相当于到这个点的一些人吃了面包走到了汇点。
然后还有一个问题，就是第一次踩的时候，不会触发，那么从原有的边中取一条出来，流量1，费用0就好了。
#include<bits/stdc++.h> using namespace std; const int maxn=200; const int INF =0x3f3f3f3f; const double esp=1e-8; struct Edge { int from,to,cap,flow; double cost; Edge(int u,int v,int ca,int f,double co):from(u),to(v),cap(ca),flow(f),cost(co){}; }; struct MCMF { int n,m,s,t; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn];//是否在队列中 double d[maxn];//距离 int p[maxn];//上一条弧 int a[maxn];//可改进量 void init(int n)//初始化 { this->n=n; for(int i=0;i<=n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap,double cost)//加边 { edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); int m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool SPFA(int s,int t,int &flow,double &cost)//寻找最小费用的增广路，使用引用同时修改原flow,cost { for(int i=0;i<n;i++) d[i]=INF; memset(inq,0,sizeof(inq)); d[s]=0;inq[s]=1;p[s]=0;a[s]=INF; queue<int> Q; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]--; for(int i=0;i<G[u].size();i++) { Edge& e=edges[G[u][i]]; if(e.cap>e.flow && d[e.to]-d[u]-e.cost>esp)//满足可增广且可变短 { d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if(!inq[e.to]) { inq[e.to]++; Q.push(e.to); } } } } if(d[t]==INF) return false;//汇点不可达则退出 flow+=a[t]; cost+=d[t]*a[t]; int u=t; while(u!=s)//更新正向边和反向边 { edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; u=edges[p[u]].from; } return true; } double MincotMaxflow(int s,int t) { int flow=0; double cost=0; while(SPFA(s,t,flow,cost)); return cost; } }MM; int main(){ int _;scanf("%d",&_); while(_--){ int n,m; scanf("%d%d",&n,&m); MM.init(n+2); for(int i=1;i<=n;i++){ int s,b; scanf("%d%d",&s,&b); int T=s-b; if(T>0) MM.AddEdge(0,i,s-b,0); else if(T<0) MM.AddEdge(i,n+1,b-s,0); } for(int i=1;i<=m;i++){ int u,v,c;double p; scanf("%d%d%d%lf",&u,&v,&c,&p); p=-log2(1.0-p);///求最大不被破坏->最小被破坏 if(c>0) MM.AddEdge(u,v,1,0); if(c-1>0) MM.AddEdge(u,v,c-1,p); } double ans=MM.MincotMaxflow(0,n+1); ans=1-pow(2,-ans); printf("%.2f ",ans); } }
View Code