题解：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.代码

#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

题解：P5814 [CTSC2001] 终极情报网

文章操作

1.题目描述

2.思路

3.注意事项

4.代码

相关推荐

评论

题解：P5814 [CTSC2001] 终极情报网