HDU 5988 最小费用流

本站寻求有缘人接手，详细了解请联系站长QQ1493399855

链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5988

题意：

n个点，每个点有a个人和b包饭，m条边，第一次经过这条边没有问题，以后每一个经过的有p概率出问题

每条边有限制，问使得所有人都有饭吃且出问题的概率最小

题解：

无向图的费用流

把相乘的取下对数变成相加的就可以用最小费用流了

代码：

 30 #include <iomanip>
 31 const double eps = 1e-8;
 32 const int MAXM = 1e5 + 7;
 33 
 34 struct node{
 35     int to, next, cap;
 36     double cost;
 37 }edge[MAXM];
 38 int head[MAXN];
 39 int pre[MAXN];
 40 int vis[MAXN];
 41 double dist[MAXN];
 42 int n, m, tot;
 43 
 44 void init() {
 45     memset(head, -1, sizeof(head));
 46     tot = 0;
 47 }
 48 
 49 void add_edge(int u, int v, int cap, double  cost) {
 50     edge[tot].to = v;
 51     edge[tot].cap = cap;
 52     edge[tot].cost = cost;
 53     edge[tot].next = head[u];
 54     head[u] = tot++;
 55     edge[tot].to = u;
 56     edge[tot].cap = 0;
 57     edge[tot].cost = -cost;
 58     edge[tot].next = head[v];
 59     head[v] = tot++;
 60 }
 61 
 62 double mcf(int s, int t, int f) {
 63     double res = 0;
 64     while (f > 0) {
 65         rep(i, 0, n + 2) {
 66             dist[i] = 1e18;
 67             vis[i] = 0;
 68             pre[i] = -1;
 69         }
 70         queue<int> q;
 71         q.push(s);
 72         dist[s] = 0;
 73         vis[s] = 1;
 74         while (!q.empty()) {
 75             int u = q.front(); q.pop();
 76             vis[u] = 0;
 77             for (int i = head[u]; i != -1; i = edge[i].next) {
 78                 int v = edge[i].to;
 79                 if (edge[i].cap > 0 && 
 80                     dist[v] > dist[u] + edge[i].cost + eps){
 81                     dist[v] = dist[u] + edge[i].cost;
 82                     pre[v] = i;
 83                     if (!vis[v]) {
 84                         vis[v] = 1;
 85                         q.push(v);
 86                     }
 87                 }
 88             }
 89         }
 90         if (dist[t] == 1e18) return -1;
 91         int d = f;
 92         for (int v = pre[t]; v != -1; v = pre[edge[v ^ 1].to])
 93             d = min(d, edge[v].cap);
 94         f -= d;
 95         res += d * dist[t];
 96         for (int v = pre[t]; v != -1; v = pre[edge[v ^ 1].to]) {
 97             edge[v].cap -= d;
 98             edge[v ^ 1].cap += d;
 99         }
100     }
101     return res;
102 }
103 
104 int main() {
105     int T;
106     scanf("%d", &T);
107     while (T--) {
108         init();
109         cin >> n >> m;
110         int s = 0, t = n + 1, f = 0;
111         rep(i, 1, n + 1) {
112             int a, b;
113             scanf("%d%d", &a, &b);
114             add_edge(s, i, a, 0);
115             add_edge(i, t, b, 0);
116             f += a;
117         }
118         while (m--) {
119             int u, v, c;
120             double p;
121             scanf("%d%d%d%lf", &u, &v, &c, &p);
122             p = -log2(1 - p);
123             if (c > 0) add_edge(u, v, 1, 0);
124             if (c > 1) add_edge(u, v, c - 1, p);
125         }
126         double p = mcf(s, t, f);
127         printf("%.2f
", 1 - pow(2, -p));
128     }
129     return 0;
130 }