#6
Time Exceeded

≥2005ms
≥512.0KiB
#7
Time Exceeded

≥2003ms
≥896.0KiB
#8
Time Exceeded

≥2004ms
≥1.625MiB

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
vector<int> e;
vector<int> cwt;
vector<int> pre;
vector<int> vis;
vector<vector<int> > cw;
vector<vector<int> > ce;
vector<double> f;
vector<double> u;
vector<double> a_s;
vector<double> a_m;
vector<vector<double> > c;
vector<vector<double> > p;
deque<int> q;

void add_edge_1(int x,int y,double c_v,double p_v)
{
    cw[x].push_back(y);
    c[x].push_back(c_v);
    p[x].push_back(p_v);
    ce[y].push_back(cw[x].size()-1);
    cw[y].push_back(x);
    c[y].push_back(0);
    p[y].push_back(-p_v);
    ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,double *flow,double *cost)
{
    f.resize(0);
    f.resize(cw.size(),0);
    f[s]=oo_max;
    e.resize(0);
    e.resize(cw.size(),-1);
    u.resize(0);
    u.resize(cw.size(),oo_max);
    u[s]=0;
    pre.resize(0);
    pre.resize(cw.size(),-1);
    pre[s]=s;
    vis.resize(0);
    vis.resize(cw.size(),0);
    for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<cw[now].size();i++)
            if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
            {
                f[cw[now][i]]=min(c[now][i],f[now]);
                e[cw[now][i]]=i;
                u[cw[now][i]]=u[now]+p[now][i];
                pre[cw[now][i]]=now;
                if (vis[cw[now][i]]==0)
                    vis[cw[now][i]]=1,q.push_back(cw[now][i]);
            }
    }
    (*flow)=f[t];
    (*cost)=u[t];
    return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,double *flow,double *cost)
{
    double temp_flow,temp_cost;
    while (bfs_1(s,t,&temp_flow,&temp_cost))
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
        (*flow)+=temp_flow;
        (*cost)+=-temp_cost*temp_flow;
    }
}

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        cw.resize(0);
        cw.resize(n+3);
        ce.resize(0);
        ce.resize(cw.size());
        c.resize(0);
        c.resize(cw.size());
        p.resize(0);
        p.resize(cw.size());
        for (int i=0;i<cw.size();i++)
        {
            cw[i].resize(0);
            ce[i].resize(0);
            c[i].resize(0);
            p[i].resize(0);
        }
        a_s.resize(0);
        a_s.resize(n+1,0);
        for (int i=1;i<=n;i++)
            scanf("%lf",&a_s[i]);
        a_m.resize(0);
        a_m.resize(n+1,0);
        for (int i=1;i<=n;i++)
            scanf("%lf",&a_m[i]);
        add_edge_1(0,cw.size()-2,m,log(double(1)));
        for (int i=1;i<=n;i++)
            if (a_m[i]>0)
                add_edge_1(cw.size()-2,i,a_m[i],-log(a_s[i]));
        cwt.resize(0);
        cwt.resize(n+1,0);
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&cwt[i]);
            if (cwt[i]==1)
                add_edge_1(i,c.size()-1,oo_max,log(double(1)));
        }
        int x,y;
        while (~scanf("%d%d",&x,&y))
            if (x>0&&y>0)
            {
                double flow,cost;
                scanf("%lf%lf",&cost,&flow);
                add_edge_1(x,y,flow,-log(cost));
                add_edge_1(y,x,flow,-log(cost));
            }
            else
                break;
        double ans_flow=0,ans_cost=0;
        min_cost_max_flow_1(0,c.size()-1,&ans_flow,&ans_cost);
        ans_cost=exp(ans_cost);
        if (ans_flow<m)
            printf("0.0000\n");
        else
        {
            int cnt;
            double temp=ans_cost;
            for (cnt=0;cnt<=16&&temp<10000;cnt++)
                temp*=10;
            string s_ans_cost;
            stringstream temp_io;
            temp_io.flush();
            temp_io<<fixed<<setprecision(cnt)<<ans_cost;
            temp_io>>s_ans_cost;
            printf("%s\n",s_ans_cost.c_str());
        }
    }
}