hdu 5988 Coding Contest 费用流
程序员文章站
2022-05-22 10:46:39
...
题目:
http://acm.split.hdu.edu.cn/showproblem.php?pid=5988
题意:
有n个区域,有m条有向边连接它们,每条边都有一个被破环的几率,但第一个人通过不会造成任何影响,之后的人通过才会有影响。现在每个区域内有一定的队员和背包,要求每个队员都拿到一个背包,且使道路奔溃的几率最小,求这个最小几率
思路:
被破坏的几率最小就是不被破坏的几率最大。可以用费用流去做,因为是乘法,那么先取log再去跑费用流,再对结果去exp即可
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10, INF = 0x3f3f3f3f;
const double eps = 1e-8;
struct edge
{
int to, cap, next;
double cost;
} g[N*N*10];
int cnt, head[N];
int pre[N];
double dis[N];
bool vis[N];
int nv;
void init()
{
cnt = 0;
memset(head, -1, sizeof head);
}
void add_edge(int v, int u, int cap, double cost)
{
g[cnt].to = u, g[cnt].cap = cap, g[cnt].cost = cost, g[cnt].next = head[v], head[v] = cnt++;
g[cnt].to = v, g[cnt].cap = 0, g[cnt].cost = -cost, g[cnt].next = head[u], head[u] = cnt++;
}
bool spfa(int s, int t)
{
for(int i = 0; i < nv; i++) dis[i] = INF;
memset(vis, 0, sizeof vis);
memset(pre, -1, sizeof pre);
queue<int> que;
que.push(s);
dis[s] = 0.0, vis[s] = true;
while(! que.empty())
{
int v = que.front(); que.pop();
vis[v] = false;
for(int i = head[v]; i != -1; i = g[i].next)
{
int u = g[i].to;
if(g[i].cap > 0 && dis[u] - dis[v] - g[i].cost > eps)//这里不取eps会tle
{
dis[u] = dis[v] + g[i].cost;
pre[u] = i;
if(! vis[u]) que.push(u), vis[u] = true;
}
}
}
return !(abs(dis[t] - INF) < eps);
}
double cost_flow(int s, int t, int flow)
{
double ans = 0;
while(flow > 0)
{
if(! spfa(s, t)) return -1;
int d = INF;
for(int i = pre[t]; i != -1; i = pre[g[i^1].to])
d = min(d, g[i].cap);
for(int i = pre[t]; i != -1; i = pre[g[i^1].to])
g[i].cap -= d, g[i^1].cap += d;
ans += d * dis[t];
flow -= d;
}
return ans;
}
int main()
{
int t, n, m;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
init();
int ss = 0, tt = n + 1;
int a, b, c;
double p;
int sum = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d%d", &a, &b);
if(a - b > 0) add_edge(ss, i, a-b, 0), sum += a-b;
if(a - b < 0) add_edge(i, tt, -(a-b), 0);
}
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d%lf", &a, &b, &c, &p);
if(c >= 1) add_edge(a, b, 1, 0);
if(c > 1) add_edge(a, b, c-1, -log(1-p));
}
nv = tt + 1;
double ans = cost_flow(ss, tt, sum);
printf("%.2f\n", 1.0 - exp(-ans));
}
return 0;
}
推荐阅读
-
HDU 5045 费用流求最大权
-
Comet OJ - Contest #6双倍快乐(最小费用流)
-
【HDU5988】Coding Contest 费用流
-
HDU - 5988 Coding Contest(最小费用流)
-
文章标题 UVALive 7740 : Coding Contest (费用流+精度)
-
HDU - 5988 Coding Contest (费用流)
-
【费用流】hdu5988 Coding Contest
-
2016青岛区域赛G题 Coding Contest 费用流
-
HDU 5988 Coding Contest(费用流)
-
HDU5988 Coding Contest(费用流)