欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}