题意:每个点i有\(s_i\)个人和\(b_i\)份食物,每个人都要找到一份食物.现在有M条有向边,从点i到点j,容量为c,第一次走过不要紧,从第二次开始就要承担\(p(0<p<1)\)的道路损坏的风险.题目保证每个人都能拿到食物,求这个风险的最小值.
分析:建立源点S和汇点T.从S到点i建容量为\(s_i\),费用为0的边;从点i到T建容量为\(b_i\),费用为0的边.
风险的最小值可以转化为求安全达成目标的. 则\(ans = \prod (1-p_i)^{k_i}\),
对ans取对数,\(log(ans) = \sum k_i*log(1-p_i)\).因为需要求这个值最大,所以费用需要取反.
因为第一次走没有风险,可以将这条容量为1的边分离出来,若容量还有剩余则建容量为\(c-1\),费用为\(-log(1-p)\)的边.
跑一遍费用流,费用取反再还原之后就是最大的安全通过的概率,1减去这个概率就是最小的风险.
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-7
const int MAXN = 10005;
const int MAXM = 100005;
const int INF = 0x3f3f3f3f;
struct Edge{
int to, next, cap, flow;
double cost;
} edge[MAXM];
int head[MAXN], tot;
int pre[MAXN];
double dis[MAXN];
bool vis[MAXN];
int N;
void init(int n)
{
N = n;
tot = 0;
memset(head, -1, sizeof(head));
}
void AddEdge(int u, int v, int cap, double cost)
{
edge[tot] = (Edge){v,head[u],cap,0,cost};
head[u] = tot++;
edge[tot] = (Edge){u,head[v],0,0,-cost};
head[v] = tot++;
}
bool spfa(int s, int t){
queue<int> q;
for (int i = 0; i <= N; i++){
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while (!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = edge[i].next){
int v = edge[i].to;
if (edge[i].cap > edge[i].flow && dis[v] - (dis[u] + edge[i].cost)> eps){
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if (!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
}
if (pre[t] == -1) return false;
else return true;
}
int minCostMaxflow(int s, int t, double &cost){
int flow = 0;
cost = 0;
while (spfa(s, t)){
int Min = INF;
for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]){
if (Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
}
for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]){
edge[i].flow += Min;
edge[i ^ 1].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}
int have[MAXN];
int need[MAXN];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d %d",&n,&m);
init(n+2);
int u,v; double w;
int s= 0, t = n+1;
for(int i=1 ; i<=n; ++i){
scanf("%d %d", &need[i], &have[i]);
}
for(int i=1;i<=n;++i){
AddEdge(s,i,need[i],0);
AddEdge(i,t,have[i],0);
}
int c;
double p;
for(int i=1;i<=m;++i){
scanf("%d %d %d %lf",&u, &v, &c, &p);
if(c >= 1) AddEdge(u,v,1,0.0);
if(c > 1) AddEdge(u,v,c-1,-log2(1.0-p));
}
double cost = 0.0;
minCostMaxflow(s,t,cost);
//cout<<cost<<endl;
printf("%.2f\n",1.0-pow(2.0,-cost));
}
return 0;
}