2016ICPCQindao G 建图网络流

Posted on | In , ,

给定n个点，m条有向边，每个点是一个吃饭的地方，每个人一盒饭。每个点有S个人，有B盒饭。每条边只能被走c次，每条边上都有电线，第一个人通过的时候，不会破坏电线，从第二个人开始，每次都有概率p破坏掉电线。使得每个人都能吃饭，求最小的破坏电线的概率

题目链接

题解

  • 朴素的建图，但要注意某个区的$S>B$，他要到别的区去取，所以源点和$S>B$连接，汇点和$S<B$连接。
  • 考虑最小的破坏电线的概率，但我们只能算(1-p)即最大的不损坏的概率
  • 考虑如何计算最大的不损坏的概率，即网络中所有费用的相乘，但网络流算法中的费用都是相加的关系，可以通过取log的方法解决这个问题(通常取log2)，跑最大费用最大流即可，最后的答案为 $1-pow(2,mincost)$。
  • 对数函数和幂函数互为反函数。
  • 在牛客上跑的挺快的，HDU上T了……

代码

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
const int maxn = 405;
const int INF=1e9+7;

struct Edge
{
    int from, to, cap, flow;
    double cost;
    Edge(int u,int v,int c,int f, double w):from(u), to(v), cap(c), flow(f), cost(w) {}
};

struct MCMF
{
    int n, m;
    vector<Edge> edges;   // 边数的两倍
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    int inq[maxn];        // 是否在队列中
    double d[maxn];          // Bellman-Ford
    int a[maxn];          // 当起点到i的可改流量
    int p[maxn];          // 最短路树上p的入弧编号(path路径)

    void init(int n)
    {
        this->n = n;
        for(int i=0; i<=n+1; i++)
            G[i].clear();
        edges.clear();
    }

    void Addedge(int from, int to, int cap,double cost)
    {
        edges.push_back(Edge(from, to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BellmanFord(int s,int t,int& flow, double& cost)
    {
        for(int i=0; i<=n; i++)
            d[i] = 1000000000+2;
        memset(inq, 0, sizeof(inq));
        d[s]=0; inq[s]=1; p[s]=0; a[s]=1000000000+2;

        queue<int> Q;
        Q.push(s);

        while(!Q.empty())
        {
            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)
                {
                    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] == 1000000000+2)
            return false;
        flow += a[t];
        cost += d[t] * 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 true;
    }

    int MincostMaxflow(int s,int t,double& cost)
    {
        int flow=0; cost=0;
        while(BellmanFord(s, t, flow, cost));
        return flow;
    }
};

int T, n, m, s[maxn], b[maxn], u, v, c;
double p;
MCMF now;

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        int st=0, ed=maxn-4;
        now.init(ed);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d", &s[i], &b[i]);
            if(b[i]>s[i])
            now.Addedge(i, ed, b[i]-s[i], 0);
            else
                now.Addedge(st, i, s[i]-b[i], 0);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d%lf", &u, &v, &c, &p);
            now.Addedge(u, v, 1, 0);
            now.Addedge(u, v, c-1, -log2(1-p));
        }
        double ans;
        now.MincostMaxflow(st, ed, ans);
        ans=-ans;
        printf("%.2f\n", 1.0-pow(2, ans));
    }
    return 0;
}