翻车笔记_ [SDOI2015] 星际战争 [网络流, 最大流, 二分, 翻车]

二分可以简化很多问题

懵逼的 题目

传送至 Luogu

扯淡的 题解

一开始以为有什么最大费用最小流什么的…
一不小心实在不会点开了标签…二分…Emmmmmmmm….

算法就很简单了…二分出一个时间, 然后按照时间连边:

  • S向激光枪连边, 容量为攻击力
  • 枪向可以攻击的人连边, 容量为INF
  • 人向T连边, 容量为装甲值

二分出解0ms稳如POI~

你以为就完了?

这里写图片描述

来告诉你什么叫卡 精 度

最后把eps设成0.00000000001…错的更多了…一气之下改成了LL…

由于这道题精度要求并不高, 而且装甲值不大, 那我们可以把 装甲值 * 10000, 然后直接用整数跑, 最后跑出来的答案除以 10000, 然后得出来比较稳健的答案, 在考场只能交一次的话还是把double转成 long long比较稳吧…但是一定要注意数据范围和精度乘起来不要超了long long…还有只要不爆空间能用long long还是用吧…可能一个关键的int就爆零了…

Update: 他们dalao管这个叫什么来着…是不是叫小数网络流来着…

沙茶的 代码

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
// 不算太毒瘤...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (1000 + 5)
#define MAXR (50 + 5)
#define MAXM (100000 + 5)
#define INF (0x7ffffffffffll)
#define eps (DD)(0.0000000001)
#define EPS (10000)
#define bh(a) ((a) + MAXR)
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define DD double
#define LL long long
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
int from;
int to;
int next;
LL flow;
LL cap;
edg() {}
edg(int a, int b, int c, LL d): from(a), to(b), next(c), flow(0), cap(d) {}
} b[MAXM << 1];
int cntb;
int g[MAXN];

int nr, ng;
int att[MAXR], hp[MAXR], dis[MAXN];
LL sumr;
LL ans;
LL dinic(int, LL);
bool bfs();
bool pd(LL);
void solve();
void adn(int, int, LL);
int main()
{
scanf("%d%d", &nr, &ng);
for (int i = 1; i <= nr; i++)
{
int srx;
scanf("%d", &srx);
srx *= EPS;
sumr += srx;
adn(bh(i), t, srx);
adn(t, bh(i), 0);
}
for (int i = 1; i <= ng; i++)
{
scanf("%d", &att[i]);
}
for (int i = 1; i <= ng; i++)
{
adn(s, i, 0);
adn(i, s, 0);
for (int j = 1; j <= nr; j++)
{
int srx;
scanf("%d", &srx);
if (srx)
{
adn(i, bh(j), INF);
adn(bh(j), i, 0);
}
}
}
solve();
printf("%lf", (DD)ans / EPS);
return 0;
}
LL dinic(int dq, LL maxf)
{
if (dq == t || !maxf)
return maxf;
LL re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if (dis[b[i].to] == dis[dq] + 1 && b[i].cap > b[i].flow)
{
LL zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
maxf -= zl;
re += zl;
b[i].flow += zl;
b[rev(i)].flow -= zl;
}
}
return re;
}
bool bfs()
{
queue<int> q;
memset(dis, 0, sizeof(dis));
q.push(s);
dis[s] = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap - b[i].flow > eps && !dis[b[i].to])
{
dis[b[i].to] = dis[dq] + 1;
q.push(b[i].to);
}
}
}
return dis[t];
}
bool pd(LL cap)
{
for (int i = 1; i <= cntb; i++)
b[i].flow = 0;
for (int i = g[s]; i; i = b[i].next)
{
b[i].cap = cap * att[b[i].to];
}
LL re = 0;
while (bfs())
re += dinic(s, INF);
return sumr == re;
}
void solve()
{
LL le = 0, ri = INF;
while (ri > le)
{
LL mi = (le + ri) >> 1;
if (pd(mi))
{
ans = mi;
ri = mi;
}
else
le = mi + 1;
}
}
void adn(int from, int to, LL cap)
{
b[++cntb] = edg(from, to, g[from], cap);
g[from] = cntb;
}
/*
2 2
2 1
6 6
1 1
0 1
*/

By 感觉OK的 Cansult