智商是真硬伤

懵逼的 题目

传送至BZOJ

扯淡的 题解

不会 一点思路都没有

woc乘起来这是闹哪样啊 感觉最短路也非常不资瓷啊

woc最后还都要乘起来 感觉网络流也不资瓷啊

看的LRJ大爷的黑书

感觉非常资瓷啊!

我万万没想到是转成对数做啊

考虑对数出现的原因: 把乘法变成加法, 把乘方变成乘法, 化简那时候很流行的天文学运算

考虑对数的性质

$\lg a \cdot b = \lg a + \lg b$

$10^{\lg x} = x$

我们就可以把乘法换成加法辣!

——在做网络流的时候对费用取对数, 然后得到答案后再把答案放到pow里面乱搞就可以辣!

woc怎么样例过不去啊…草草草保留有效数字不是保留小数woc…Emmmmmmmmm…感觉不资瓷啊…问了问MHR…搞了一个奇怪的方法…Emmmmmmm…

woc怎么样例过不去啊…调了一上午…怎么感觉我写的程序没啥问题啊…手玩了一下样例…发现我程序写的却实没问题啊…woc难道不是输出$0$ ?????

我万万没想到啊

间谍传信息$^{tm}$是双向边啊

然后WAWA…

woc最后忘判断$ans$是不是小于$eps$了…

然后WA…

woc怎么还不过啊…去COGS下载…Emmmmmm还有概率为1的情况…Emmmmmm…特判 AC…

Emmmmmm…

沙茶的 代码

Cansult的代码——又臭又长

/**************************************************************
    Problem: 2542
    User: Cansult
    Language: C++
    Result: Accepted
    Time:868 ms
    Memory:8756 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define INF (0X7FFFFFF)
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define LD double
const LD eps = 0.0000000000001;
const int s = 0, t = MAXN - 1, ss = MAXN - 2;
int k;
using namespace std;
struct edg
{
    int from, to, next, cap, flow;
    LD cost;
    edg() {}
    edg(int fr, int dqt, int ne, int ca, LD co): from(fr), to(dqt), next(ne), cap(ca), flow(0), cost(co) {}
}b[MAXN << 1];
int g[MAXN], cntb, pre[MAXN];
LD ans;
void adn(int from, int to, int cap, LD cost)
{
    b[++cntb] = edg(from, to, g[from], cap, cost);
    g[from] = cntb;
}
int spfa()
{
    LD dis[MAXN];
    bool inq[MAXN];
    int a[MAXN];
    memset(a, 0, sizeof(a));
    memset(inq, false, sizeof(inq));
    memset(dis, 0xc2, sizeof(dis));
    queue<int> q;
    q.push(ss);
    dis[ss] = 0;
    a[ss] = INF;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        inq[dq] = false;
        for (int i = g[dq]; i; i = b[i].next)
            if (b[i].cap > b[i].flow && dis[b[i].to] < dis[dq] + b[i].cost - eps)
            {
                a[b[i].to] = min(a[dq], b[i].cap - b[i].flow);
                dis[b[i].to] = dis[dq] + b[i].cost;
                pre[b[i].to] = i;
                if (!inq[b[i].to])
                    q.push(b[i].to), inq[b[i].to] = true;
            }
    }
    return a[t];
}
void solve()
{
    int dans = 0;
    while (true)
    {
        int zl = spfa();
        dans += zl;
        if (!zl)
            break;
        for (int i = t; i != ss; i = b[pre[i]].from)
        {
            ans += (LD)zl * b[pre[i]].cost;
            b[pre[i]].flow += zl;
            b[rev(pre[i])].flow -= zl;
        }
    }
    if (dans != k)
    {
        puts("0.0000");
        exit(0);
    }
}
void init()
{
    int n;
    scanf("%d%d", &n, &k);
    adn(ss, s, k, 0);
    adn(s, ss, 0, 0);
    LD cs[MAXN];
    for (int i = 1; i <= n; i++)
        scanf("%lf", &cs[i]), cs[i] = (cs[i] ? log(cs[i]) : -INF);
    for (int i = 1; i <= n; i++)
    {
        int srx;
        scanf("%d", &srx);
        if (cs[i] <= -INF)
            continue;
        adn(s, i, srx, cs[i]);
        adn(i, s, 0, -cs[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        int srx;
        scanf("%d", &srx);
        if (srx)
        {
            adn(i, t, INF, 0);
            adn(t, i, 0, 0);
        }
    }
    while (true)
    {
        int srx, sry, srz;
        LD co;
        scanf("%d%d", &srx, &sry);
        if (srx == -1 && sry == -1)
            break;
        scanf("%lf%d", &co, &srz);
        co = log(co);
        adn(sry, srx, srz, co);
        adn(srx, sry, 0, -co);
        adn(srx, sry, srz, co);
        adn(sry, srx, 0, -co);
    }
}
void print(LD x)
{
    int wz;
    for (wz = 1; x < 10000; wz++)
        x *= 10;
    int gg = x;
    wz -= 6;
    if (x - gg  >= 0.5)
        ++gg;
    printf("0.");
    for (int i = 1; i <= wz; i++)    printf("0");
    printf("%d", gg);
}
int main()
{
    init();
    solve();
    ans = pow(M_E, ans);
    if (ans >= 1 - eps)
        printf("1.0000");
    else if (ans > eps)
        print(ans);
    else
        puts("0.0000");
    return 0;
}

/*
6 13
0.9 0.7 0.8 0 0 0 2 6 8 0 0 0
0 0 0 1 0 1
1 4 0.5 2
2 3 0.9 5
2 5 0.8 2
2 6 0.8 7
3 5 0.8 2
5 6 0.8 4
-1 -1
*/

By 没有智商cyk