做题记录1

P3324 [SDOI2015] 星际战争

思路

如果花费 \(T\) 时间可以消灭所有的机器人，显然大于 \(T\) 的时间也可以。具有单调性，考虑二分答案。

设当前二分的时间为 \(x\) ，对于第 \(i\) 个武器，它能造成的伤害为 \(b_i \times x\) 。设武器所在的集合为 \(L\) ，机器人所在的集合为 \(R\) ，将每个武器和它能攻击到的机器人连一条边，就形成了二分图，因此问题转化为了判断是否满足

\[\sum b_i \times t > \sum a_i \]

可以再连一个流量无限的源点和汇点，用最大流解决这个问题。

具体的建图细节：

对于源点到 \(L\) 到每个点，建一条流量为 \(b_i \times x\) 的边；对于 \(L\) 和 \(R\) 之间的点，建流量为 \(+ \infty\) 的边；对于 \(R\) 的每个点到汇点的点，建一条流量为 \(a_i\) 的边。

代码

#include<bits/stdc++.h>
#define x first
#define y second
using i64 = long long;
using u64 = unsigned long long;
using u128 = __uint128_t;
using PII = std::pair<int, int>;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int INF = 1e9;
const double eps = 1e-6;
struct flow {int cnt = 1, hd[N], nxt[M * 2], to[M * 2];double limit[M * 2];void add(int u, int v, double w) {nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v, limit[cnt] = w;nxt[++cnt] = hd[v], hd[v] = cnt, to[cnt] = u, limit[cnt] = 0;}int T, dis[N], cur[N];double dfs(int id, double res) {if(id == T) return res;double flow = 0;for(int i = cur[id]; i && res > eps; i = nxt[i]) {cur[id] = i;double c = std::min(res, (double)limit[i]); int it = to[i];if(dis[id] + 1 == dis[it] && c > eps) {double k = dfs(it, c);if(k > eps) {flow += k, res -= k, limit[i] -= k, limit[i ^ 1] += k;}}}if(flow <= eps) dis[id] = -1;return flow;}double maxflow(int s, int t) {T = t;double flow = 0;while(1) {std::queue<int> q;memcpy(cur, hd, sizeof(hd));memset(dis, 0xff, sizeof(dis));q.push(s), dis[s] = 0;while(q.size()) {int u = q.front();q.pop();for(int i = hd[u]; i; i = nxt[i]) {if(dis[to[i]] == -1 && limit[i] > eps) {dis[to[i]] = dis[u] + 1;q.push(to[i]);}}}if(dis[t] == -1) return flow;flow += dfs(s, 1e18);}}
};
void solve(void) {int n, m; std::cin >> n >> m;std::vector<int> a(n + 1);std::vector<int> b(m + 1);double sum = 0;for(int i = 1; i <= n; i++) {std::cin >> a[i];sum += a[i];}for(int i = 1; i <= m; i++) std::cin >> b[i];bool st[51][51] = {0};for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {std::cin >> st[i][j];}}flow g;auto check = [&](double x) -> bool {g.cnt = 1;memset(g.hd, 0, sizeof(g.hd));int s = 0;int L = 1, R = L + m, t = R + m + n;for(int i = 1; i <= m; i++) {g.add(s, L + i, (double)b[i] * x);}for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {if(st[i][j]) g.add(L + i, R + j, INF);}}for(int i = 1; i <= n; i++) {g.add(R + i, t, a[i]);}return g.maxflow(s, t) + eps >= sum;};double l = 0, r = 1e9, ans = -1;while(r - l >= eps) {double mid = (l + r) / 2;if(check(mid)) {ans = mid;r = mid;} else l = mid;}std::cout << std::fixed << std::setprecision(6) << ans;
}
int main(void) {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;//std::cin >> t;while(t--) solve();return 0;
}