P5814 [CTSC2001] 终极情报网

发表于 阅读次数：

1.题目描述

有 \(N\) 名间谍，分别用数字 \(1,2,\cdots,N\) 编号。间谍可以双向联系。\([0,1]\) 的实数 \(S_{i,j}\) 表示第 \(i\) 和第 \(j\) 名间谍联系的安全程度，正整数 \(M_{i,j}\) 表示他们这次联系时能够互相传递的消息的最大数目。\([0,1]\) 的实数 \(AS_j\) 表示总部与间谍 \(j\) 之间进行联系的安全程度，正整数 $AM_j $ 表示总部和间谍 \(j\) 之间传递的消息的最大数目。消息从间谍手中交到敌军的过程是绝对安全的。

现在总部有 \(K\) 条假消息，求传递所有消息的最大安全程度。

2.思路

本题可以用费用流模型解决。每条边 \((i, j)\) 的流量上限为 \(M_{i, j}\)，费用为 \(S_{i, j}\)。建图时要加入三个点 \(S, s, t\)，其中 \(S\) 向 \(s\) 连一条费用是 \(1\)，流量上限是 \(K\) 的边，保证最大流不超过 \(K\)。\(s\) 和 \(t\) 分别表示总部和敌军总部，\(s\) 向所有点 \(i\) 连流量上限为 \(AM_i\)，费用为 \(AS_i\) 的边，所有点向 \(t\) 连流量上限为 \(\infty\)，费用为 \(1\) 的边。其余连双向边建图即可。

对与本题，费用流的bfs过程需要处理 \(s\) 到每个点路径的最大安全度乘积。即 \(dis_i = \max_{(j, i) \in E} \{dis_j * S_{j, i}\}, dis_s=1\)。每次产生新的流 \(f\) 时，将答案加上 \(dis_t ^ f\)。注意在各种比大小时加一个 \(eps\)。

3.注意事项

  • 与常规费用流不同，本题的费用累计方式是乘而不是加。建图时一组反向边的费用应该互为倒数。
  • 特别注意本题的输出，由于需要保留 \(5\) 位有效数字，所以向 \(0.01\) 这种答案要补足到 \(0.010000\)，不能直接使用cout.precision(5)，手写一个输出函数即可解决问题。

4.代码

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
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
using namespace std;

using ld = long double;
const int N = 310;
const ld eps = 1e-12;
struct Edge {
    int v, rev, c;
    ld w;
};
vector<Edge> gh[N];
int cur[N], M[N];
ld dis[N], Ans = 1, S[N], dep[N];
bitset<N> vis;
ld qpow(ld a, int b) {
    ld ans = 1;
    for (; b; b >>= 1) {
        if (b&1) ans *= a;
        a *= a;
    }
    return ans;
}
void add(int u, int v, int c, ld w) {
    // vector存图记录反向边编号。
    gh[u].push_back({v, (int)gh[v].size(), c, w});
    gh[v].push_back({u, (int)gh[u].size()-1, 0, 1.0/w});
}
ld bfs(int s, int t) {
    memset(dis, 0, sizeof(dis));
    memset(dep, 0, sizeof(dep));
    vis = 0;
    dis[s] = 1, dep[s] = 1;
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (auto e : gh[u]) {
            if (e.c > 0 && dis[u] * e.w - dis[e.v] > eps) {
                dis[e.v] = dis[u] * e.w, dep[e.v] = dep[u] + 1;
                if (!vis[e.v]) q.push(e.v);
            }
        }
    }
    return dis[t];
}
int dfs(int u, int t, int fl) {
    if (u == t || !fl) return fl;
    int ret = 0;
    for (int& i = cur[u]; i < gh[u].size(); i++) {
        auto& e = gh[u][i];
        if (e.c > 0 && abs(dis[e.v] - dis[u] * e.w) <= eps && dep[e.v] == dep[u] + 1) {
            int f = dfs(e.v, t, min(fl, e.c));
            if (f > 0) {
                ret += f;
                fl -= f;
                e.c -= f;
                gh[e.v][e.rev].c += f;
                if (fl == 0) break;
            }
        }
    }
    return ret;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t) > eps) {
        memset(cur, 0, sizeof(cur));
        int x;
        while ((x = dfs(s, t, INT_MAX)))
            ans += x, Ans *= qpow(dis[t], x);
    }
    return ans;
}
void deal() {
    char ch[40];
    double ans = Ans;
    sprintf(ch,"%.15lf\n",ans);
    int sum = 0,i;
    for (i = 0; sum < 5; i++)
        if ((ch[i]!='0' && ch[i]!='.') | (sum>0))
            sum++;
    if (ch[i] >= '5')
        ch[i-1]++;
    ch[i] = 0;
    for(; i >= 0; i--) {
        if (ch[i] == '.') break;
        else if (ch[i] > '9')
            ch[i-1]++, ch[i] = '0';
    }
    printf("%s\n",ch);
}

int main() {
    // freopen("agent.in", "r", stdin);
    // freopen("agent.out", "w", stdout);
    int n, k;
    cin >> n >> k;
    int s = n+1, t = n+2, s1 = n+3;
    for (int i = 1; i <= n; i++)
        cin >> S[i];
    for (int i = 1; i <= n; i++)
        cin >> M[i];
    for (int i = 1; i <= n; i++)
        add(s, i, M[i], S[i]);
    for (int i = 1; i <= n; i++) {
        int ok;
        cin >> ok;
        if (ok)
            add(i, t, INT_MAX, 1);
    }
    add(s1, s, k, 1);
    while (true) {
        int u, v, c;
        ld w;
        cin >> u >> v;
        if (u == -1 && v == -1) break;
        cin >> w >> c;
        add(u, v, c, w);
        add(v, u, c, w);
    }
    int fl = dinic(s1, t);
    if (fl != k) cout << "0.0000" << endl;
    else deal();
    return 0;
}

The End