题意：
给出n个点和m条边，每个点有si个人，bi份食物,每条边一开始可以通过一个人,后来的人每通过一个就有pi的概率使整个系统崩溃,问崩溃的最小的概率是多少
思路：
对于崩溃的最小概率，由于只有一条奔溃就会全部崩溃，那么将所有不会崩溃的概率相乘就是不会奔溃的概率，所以崩溃的概率 = 1 - 不会崩溃的概率，所以要求最大不会崩溃的概率，那么我们只要对不会崩溃的概率取反即可
一开始想到了网络流，但是对于概率相乘不知道如何处理，然后学到了一个公式：
log(a)+log(b)+log(c)==log(a∗b∗c)
所以费用为 −log(1−pi)
由于点从1到n，于是我们可以建立一个以0为源点，以n+1为汇点的图。
每个区域如果有食物和人，那么人先吃掉食物是最优的。
如果食物过量的点，我们可以建一条边从源点到该点，容量是过量的食物数量，费用是0；
如果人数过量的点，我们可以建一条边从该点到汇点，容量是过量的人数，费用是0。
剩下的就是图中的m条边，对于每条边分解成两条边，为：
从u到v，容量是1，费用是0；从u到v，容量是cap-1，费用为 −log(1−pi)
据此，跑一遍最小费用最大流即可
我用的是kuangbin的SPFA的模板，一开始T了一发，不会图论，想不明白为什么会T
于是套了zkw费用流板子
AC_code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXM = 20000;
const int INF = 0x3f3f3f3f;
struct Edge {
int to,next,cap,flow;
double cost;
Edge(int _to = 0,int _next = 0,int _cap = 0,int _flow = 0,double _cost = 0):
to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost) {}
} edge[MAXM];
struct ZKW_MinCostMaxFlow {
int head[MAXN],tot;
int cur[MAXN];
double dis[MAXN];
bool vis[MAXN];
int ss,tt,N;//源点、汇点和点的总个数（编号是 0～N-1）, 不需要额外赋值，调用会直接赋值
int max_flow;
double min_cost;
void init() {
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++;
}
int aug(int u,int flow) {
if(u == tt)return flow;
vis[u] = true;
for(int i = cur[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if(edge[i].cap > edge[i].flow && !vis[v] && dis[u] ==dis[v] + edge[i].cost) {
int tmp = aug(v,min(flow,edge[i].cap - edge[i].flow));
edge[i].flow += tmp;
edge[i^1].flow -= tmp;
cur[u] = i;
if(tmp)return tmp;
}
}
return 0;
}
bool modify_label() {
double d = INF;
for(int u = 0; u < N; u++)
if(vis[u])
for(int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if(edge[i].cap>edge[i].flow && !vis[v])
d = min(d, dis[v]+edge[i].cost - dis[u]);
}
if(d == INF)return false;
for(int i = 0; i < N; i++)
if(vis[i]) {
vis[i] = false;
dis[i] += d;
}
return true;
}
/* * 直接调用获取最小费用和最大流 * 输入: start-源点，end-汇点，n-点的总个数（编号从 0 开始） * 返回值: pair<int,int> 第一个是最小费用，第二个是最大流 */
pair<double,int> mincostmaxflow(int start,int end,int n) {
ss = start, tt = end, N = n;
min_cost = max_flow = 0;
for(int i = 0; i < n; i++)dis[i] = 0;
while(1) {
for(int i = 0; i < n; i++)cur[i] = head[i];
while(1) {
for(int i = 0; i < n; i++)vis[i] = false;
int tmp = aug(ss,INF);
if(tmp == 0)break;
max_flow += tmp;
min_cost += tmp*dis[ss];
}
if(!modify_label())break;
}
return make_pair(min_cost,max_flow);
}
} solve;
int main() {
int t, n, m, a, b, u, v, cap;
double cost;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
solve.init();//n个点 + 源点0 + 汇点 n+1
for(int i = 1; i <= n; i++) {
scanf("%d %d", &a, &b);
a -= min(a, b);
b -= min(a, b);
if(a > 0) {
solve.addedge(0, i, a, 0);
} else {
solve.addedge(i, n+1, b, 0);
}
}
for(int i = 1; i <= m; i++) {
scanf("%d %d %d %lf", &u, &v, &cap, &cost);
if(cap > 0) {
solve.addedge(u, v, 1, 0);
}
if(cap-1 > 0) {
solve.addedge(u, v, cap-1, -1*log(1.0-cost));
}
}
pair<double, int> ans = solve.mincostmaxflow(0, n+1, n+1);
double q = ans.first;
q = 1.0 - exp(-1.0*q);
printf("%.2lf\n", q);
}
return 0;
}
京公网安备 11010502036488号