【CTSC2001】终极情报网 | Mrsrz's blog

费用流

题目大意：

给定 $n$ 个人，每个人可以从情报站获取一定信息，有些可以传送给对方情报站。人与人之间可以传送一定信息。

情报站传给人，人传给人一条信息，有一个安全度（$\in [0,1]$）。而人传给情报站绝对安全。一条信息从己方情报站传给对方情报站的安全度为经过的路径的安全度之积。

求发送 $k$ 条信息的最大安全度之和。

题解：

直接连边跑最大费用最大流即可。

但是这里的贡献算的是乘积而不是和。

我们对每个数取 $\ln$ 作为费用，就转化为加和的问题了。

最后再对答案取 $\exp$ 即为真实答案。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define double long double
using namespace std;
const int N=2005,inf=0x3f3f3f3f;
int n,k,head[N],cnt=1,T,TT,flow,a[N],pre_e[N];
double as[N],ans,dis[N];
queue<int>q;
bool vis[N];
struct edge{
    int to,nxt,cap;double cost;
}e[N*N];
inline void addedge(int u,int v,int cap,double cost){
    e[++cnt]=(edge){v,head[u],cap,cost},head[u]=cnt;
}
bool MCMF(){
    for(int i=1;i<=TT;++i)dis[i]=-1e36;
    dis[0]=0;
    memset(pre_e,0,sizeof pre_e);
    memset(a,0,sizeof a);
    a[0]=inf;
    for(q.push(0);!q.empty();){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
            if(e[i].cap&&dis[u]+e[i].cost-dis[e[i].to]>1e-12){
                dis[e[i].to]=dis[u]+e[i].cost;
                a[e[i].to]=min(e[i].cap,a[u]);
                pre_e[e[i].to]=i;
                if(!vis[e[i].to])vis[e[i].to]=1,q.push(e[i].to);
            }
    }
    if(a[TT]==0)return 0;
    flow+=a[TT];ans+=dis[TT]*a[TT];
    for(int i=TT;i;i=e[pre_e[i]^1].to){
        e[pre_e[i]].cap-=a[TT];
        e[pre_e[i]^1].cap+=a[TT];
    }
    return 1;
}
void write(double s){
    int w=0;
    for(long long x=1;;x*=10){
        long long b=(long long)(x*s+.5);
        if(b>=10000){
            char ss[50]="";
            sprintf(ss,"%%.%dLf\n",w);
            printf(ss,(double)b/x);
            return;
        }
        ++w;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>k;
    T=n+1,TT=n+2;
    addedge(T,TT,k,0),addedge(TT,T,0,0);
    for(int i=1;i<=n;++i)
        cin>>as[i],as[i]=logl(as[i]);
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        addedge(0,i,x,as[i]);
        addedge(i,0,0,-as[i]);
    }
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        if(x)
            addedge(i,T,inf,0),addedge(T,i,0,0);
    }
    for(int x,y;cin>>x>>y,(x>=0&&y>=0);){
        double s;int m;
        cin>>s>>m;
        s=logl(s);
        addedge(x,y,m,s);
        addedge(y,x,0,-s);
        addedge(y,x,m,s);
        addedge(x,y,0,-s);
    }
    while(MCMF());
    if(flow<k)puts("0");else write(expl(ans));
    return 0;
}