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

读完题后不难看出本题是个网络流模型，源点流出的总流量为\(k\)，源点向每个和总部直接联系的间谍连边，每个间谍向其能传递的间谍连容量为\(m\)的边，能与德军情报部进行联系的间谍向汇点连容量为\(inf\)的边，若最大流为\(k\)，则存在可行的方案。

处理可靠程度最大时，考虑用费用流解决，将每条边的安全程度看作边的费用，进行最大费用最大流即可，注意反向边的费用应该为原边费用的倒数，实现时把平时的费用流的一些部分改为乘法即可。

一些细节看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 1000010

#define inf 1000000000

#define eps 1e-12

using namespace std;

typedef long double ld;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,k,S,s,t;

ld ans=1;

int am[maxn],d[maxn];

ld as[maxn],dis[maxn];

bool vis[maxn];

char str[30];

struct edge

{

    int to,nxt,v;

    ld c;

}e[maxn];

int head[maxn],edge_cnt=1;

void add(int from,int to,int val,ld cost)

{

    e[++edge_cnt]=(edge){to,head[from],val,cost};

	head[from]=edge_cnt;

    e[++edge_cnt]=(edge){from,head[to],0,1/cost};

	head[to]=edge_cnt;

}

bool spfa()

{

    queue<int> q;

    for(int i=s;i<=t;++i) dis[i]=0,vis[i]=d[i]=0;

    q.push(s),dis[s]=1,d[s]=1,vis[s]=true;

    while(!q.empty())

    {

        int x=q.front();

        q.pop(),vis[x]=false;

        for(int i=head[x];i;i=e[i].nxt)

        {

            int y=e[i].to,v=e[i].v;

            ld c=e[i].c;

            if(v&&dis[x]*c-dis[y]>eps)

            {

                dis[y]=dis[x]*c,d[y]=d[x]+1;

                if(!vis[y]) vis[y]=true,q.push(y);

            }

        }

    }

    return dis[t];

}

int dfs(int x,int lim)

{

    if(x==t) return lim;

    int res=lim,flow;

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to,v=e[i].v;

        ld c=e[i].c;

        if(!v||dis[y]-dis[x]*c>eps||d[y]!=d[x]+1) continue;

        if(flow=dfs(y,min(res,v)))

        {

            res-=flow;

            e[i].v-=flow;

            e[i^1].v+=flow;

            if(!res) break;

        }

    }

    return lim-res;

}

ld qp(ld x,int y)

{

    ld v=1;

    while(y)

    {

        if(y&1) v*=x;

        x*=x,y>>=1;

    }

    return v;

}

void dinic()

{

    int flow,sum=0;

    while(spfa()>eps)

        while(flow=dfs(s,inf))

            sum+=flow,ans*=qp(dis[t],flow);

    if(sum!=k) ans=0;

}

void print()

{

    sprintf(str,"%.15Lf",ans);

    int pos=0,cnt=0;

    while(cnt<5)

    {

        char ch=str[pos++];

        if((ch!='0'&&ch!='.')||cnt) cnt++;

    }

    if(str[pos]>='5') str[pos-1]+=1;

    str[pos]=0;

    for(int i=pos;i>=0;--i)

    {

        if(str[i]=='.') break;

        if(str[i]>'9') str[i-1]++,str[i]='0';

    }

    printf("%s",str);

}

int main()

{

    read(n),read(k),S=n+1,t=S+1,add(s,S,k,1);

    for(int i=1;i<=n;++i) scanf("%Lf",&as[i]);

    for(int i=1;i<=n;++i) read(am[i]);

    for(int i=1;i<=n;++i)

        if(am[i]&&as[i]>eps)

            add(S,i,am[i],as[i]);

    for(int i=1;i<=n;++i)

    {

        int v;

        read(v);

        if(v) add(i,t,inf,1);

    }

    while(1)

    {

        int x,y,m;

        ld s;

        read(x),read(y);

        if(x==-1&&y==-1) break;

        scanf("%Lf",&s),read(m);

        add(x,y,m,s),add(y,x,m,s);

    }

    dinic();

    if(ans>eps) print();

    else puts("0");

    return 0;

}