题解 P5814 【[CTSC2001]终极情报网】

· · 题解

因为实在太坑人了，就写一篇题解。

首先，本题费用流的模型是很明显的——我军总部连到每个人，两个人之间互相连边，然后每个人再连到敌军总部。

但是，这里的费用却比较非常规——它是路径上所有边的边权的乘积。

若仍然暴力跑费用流的话，可能会出现除零这种奇怪的东西，因此对所有边权取个 \ln 即可化积为和，然后最后把跑出来的最小费用再给它 \exp 回去就行了。

需要注意的是，因为这题的边权都是实数，就可能会把 SPFA 可以处理的零环给判成负环，于是在比较大小的时候得手动加一个 \text{eps} 上去。

同时，注意输出——“保留 5 位有效数字”的意思是，找到小数点后第一个非 0 位，从该位往后再取 5 位作四舍五入，并非保留 5 位小数。

代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=-0x3f3f3f3f;
const double eps=1e-8;
const double lim=-100;
int n,m,s;
namespace MCMF{
    const int N=310,M=2000000;
    int head[N],cnt,fr[N],S,T,flow;
    double cost,dis[N];
    struct node{
        int to,next,val;
        double cost;
    }edge[M];
    void ae(int u,int v,int w,double c){
//      printf("%d %d %d %lf\n",u,v,w,c);
        edge[cnt].cost=c,edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].cost=-c,edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    queue<int>q;
    bool in[N];
    bool SPFA(){
        for(int i=1;i<=T;i++)dis[i]=inf;dis[S]=0,q.push(S),in[S]=true;
        while(!q.empty()){
            int x=q.front();q.pop(),in[x]=false;
            for(int i=head[x];i!=-1;i=edge[i].next){
                if(!edge[i].val)continue;
                if(dis[edge[i].to]+eps<dis[x]+edge[i].cost){
                    dis[edge[i].to]=dis[x]+edge[i].cost,fr[edge[i].to]=i;
                    if(!in[edge[i].to])in[edge[i].to]=true,q.push(edge[i].to);
                }
            }
        }
        if(dis[T]<=inf+eps)return false;
        int x=T,mn=0x3f3f3f3f;
        while(x!=S)mn=min(mn,edge[fr[x]].val),x=edge[fr[x]^1].to;
        flow+=mn,cost+=dis[T]*mn,x=T;
        while(x!=S)edge[fr[x]].val-=mn,edge[fr[x]^1].val+=mn,x=edge[fr[x]^1].to;
        return true;
    }
}
using namespace MCMF;
double sft[310];
char str[310];
void roundprint(double x){
    sprintf(str,"%.10lf",x);
    int len=0,sml=-1;
    for(len=0;sml<4;len++)if(str[len]>'0'&&str[len]<='9'||sml!=-1)sml++;
    if(str[len]>='5')str[len-1]++;str[len]='\0';
    while(str[len-1]!='.'&&str[len-1]>'9')str[len-1]='0',str[len-2]++,len--;
    printf("%s\n",str);
}
int main(){
    scanf("%d%d",&n,&m),s=n+1,S=n+2,T=n+3,memset(head,-1,sizeof(head)),ae(S,s,m,0);
    for(int i=1;i<=n;i++)scanf("%lf",&sft[i]);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(sft[i]>eps)ae(s,i,x,log(sft[i]));
        else ae(s,i,x,lim);
    }
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x)ae(i,T,0x3f3f3f3f,0);
    }
    while(true){
        int x,y,z;double c;
        scanf("%d%d",&x,&y);
        if(x==-1&&y==-1)break;
        scanf("%lf%d",&c,&z);
        if(c>eps)ae(x,y,z,log(c)),ae(y,x,z,log(c));
        else ae(x,y,z,lim),ae(y,x,z,lim);
    }
    while(SPFA());
    if(flow!=m)puts("0");else roundprint(exp(cost));
    return 0;
}