青岛G,

Posted by Cww97 on 2016-12-16

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/53693445
hdu5988
费用流加个log
记得EPS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 2007;
const int INF=0x3f3f3f3f;
const double EPS = 1e-8;
struct MCMF{
struct Edge{
int from,to,cap,flow;
double cost;
Edge(int x,int y,int z,int u,double v){
from=x;to=y;cap=z;flow=u;cost=v;
}
};
vector <Edge> edges;
vector <int > G[N];
int n, m, s, t;
int inq[N], p[N], a[N];
double d[N];
inline void Init(int n,int s,int t){
this->n = n;
this->s = s;
this->t = t;
edges.clear();
for (int i=1;i<=n;i++)G[i].clear();
}
inline void AddEdge(int f,int t,int c,double w){
edges.push_back(Edge(f,t,c,0, w));
edges.push_back(Edge(t,f,0,0,-w));
int top = edges.size();
G[f].push_back(top-2);
G[t].push_back(top-1);
}
bool spfa(int s,int t,int flow,double &cost){
for (int i=0;i<=n+1;i++)d[i]=INF;
d[t] = INF;
memset(inq,0,sizeof(inq));
d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;
queue<int>Q;Q.push(s);
//puts("???");
for (;!Q.empty();){
//puts("???");
int u =Q.front();Q.pop();inq[u]=0;
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+EPS)continue;
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]){Q.push(e.to);inq[e.to]=1;}
}
}
if (d[t] >= INF)return 0;//false
flow += a[t];
cost +=(double)d[t] * (LL)a[t];
for (int u=t;u!=s;u=edges[p[u]].from){
edges[p[u] ].flow += a[t];
edges[p[u]^1].flow -= a[t];
}
return 1;//true
}
///需要保证初始网络中没有负权
double mcmf(int s,int t){
int flow =0;
double cost = 0;
for (;spfa(s,t,flow,cost);){
//printf("cost = %.2lf\n",cost);
}
return cost;
}///MinCostMaxFlow
}g;
int main(){
//freopen("in.txt", "r", stdin);
//freopen("out.txt","w", stdout);
int T, x, y, z, n, m;
scanf("%d", &T);
for (double p; T--;){
scanf("%d%d", &n, &m);
g.Init(n, 0, n+1);
int s = 0, t = n+1;
for (int i=1; i<=n ;i++){
scanf("%d%d", &x, &y);
g.AddEdge(s, i, x, 0.0);
g.AddEdge(i, t, y, 0.0);
}
for (int i=1; i<=m; i++){
scanf("%d%d%d%lf",&x,&y,&z,&p);
p = - log(1 - p);
g.AddEdge(x, y, z-1, p);
g.AddEdge(x, y, 1 , 0);
}
double ans = -g.mcmf(s,t);
//printf("ans = %.2lf\n",ans);
printf("%.2lf\n", 1 - exp(ans));
}
return 0;
}