翻车笔记_ [Ctsc2001]终极情报网 [网络流, 费用流, 清奇脑回路]

智商是真硬伤

懵逼的 题目

传送至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的代码——又臭又长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/**************************************************************
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