题解

题目分析

这是一道基于网络流的最大费用流问题，需要选择$k$个物品使得总价值最大。

解题思路

1. 问题转化

• 将每个物品的价值取对数，将乘法转化为加法
• 使用网络流模型：源点$s$ → 超级源点$S$ → 物品节点 → 汇点$t$
• 每条边的费用为物品价值的对数值

2. 网络流建模

• 源点$s$: 限制总流量为$k$
• 超级源点$S$: 连接所有物品节点
• 物品节点: 每个物品的容量为$m[i]$，费用为$\log(co[i])$
• 汇点$t$: 只有特定物品($op=1$)可以流向汇点
• 物品间连接: 双向边，容量为$c$，费用为$\log(w)$

3. 算法实现

• 使用Dinic算法求解最大费用流
• 通过SPFA算法寻找最长路径（费用最大）
• 使用DFS进行增广路径查找

4. 关键技巧

• 对数值计算避免精度问题
• 自定义Print函数处理输出格式
• 检查最大流是否等于$k$来判断是否有解

时间复杂度

$O(V^2E)$，其中$V$为节点数，$E$为边数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e5 + 5, inf = 1e9;
const ll INF = 1e18;
const ld eps = 1e-12;
struct Node { int v, nxt, c; ld w; } e[N*2];
int head[N], cnt = 1, now[N], s, S, t, n, k, m[N]; ld dis[N], sum, co[N]; bool vis[N];
void Add(int u, int v, int c, ld w) {
    e[++cnt] = {v, head[u], c, w}; head[u] = cnt;
    e[++cnt] = {u, head[v], 0, -w}; head[v] = cnt;
}
queue <int> q;
bool spfa() {
    for(int i = 1; i <= t; i++) dis[i] = -1e12;
    memset(vis, 0, sizeof(vis));
    while(!q.empty()) q.pop(); q.push(s); dis[s] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = false, now[u] = head[u];
        // printf("%d\n", u);
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v; ld w = e[i].w;
            if(e[i].c && dis[v] <= dis[u] + w - eps) {
                dis[v] = dis[u] + w;
                if(!vis[v]) { q.push(v); vis[v] = true; }
            }
        }
    }
    return dis[t] != -1e12;
}
int dfs(int u, int flow) {
    if(u == t || !flow) return flow;
    int rest = flow; vis[u] = true;
    for(int i = now[u]; i && rest; i = e[i].nxt) {
        int v = e[i].v; now[u] = i; ld w = e[i].w;
        if(e[i].c && !vis[v] && abs(dis[v] - dis[u] - w) <= eps) {
            int k = dfs(v, min(rest, e[i].c));
            if(k) rest -= k, e[i].c -= k, e[i^1].c += k;
        }
    }
    vis[u] = false;
    return flow - rest;
}
int dinic() {
    int maxflow = 0, flow = 0;
    while(spfa()) while(flow = dfs(s, inf)) maxflow += flow, sum += dis[t] * flow;
    return maxflow;
}
void Print(ld ans) {
    char ch[40]; sprintf(ch, "%.15Lf\n", ans);
    int cnt = 0, i = 0;
    for(i = 0; cnt < 5; i++)
        if(cnt || (ch[i] != '0' && ch[i] != '.')) cnt++;
    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() {
    scanf("%d%d", &n, &k); S = n + 1, t = n + 2, s = n + 3;
    for(int i = 1; i <= n; i++) scanf("%LF", &co[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &m[i]);
    for(int i = 1; i <= n; i++) Add(S, i, m[i], log(co[i]));
    for(int i = 1; i <= n; i++) {
        int op; scanf("%d", &op);
        if(op) Add(i, t, inf, 0);
    }
    while(true) {
        int u, v, c; ld w; scanf("%d%d", &u, &v);
        if(u == -1 && v == -1) break;
        scanf("%Lf%d", &w, &c);
        Add(u, v, c, log(w)); Add(v, u, c, log(w));
    }
	Add(s, S, k, 0);
    int ret = dinic();
    if(ret != k) printf("0.00000\n");
    else Print(exp(sum));
	return 0;
}