BZOJ 3993 [SDOI 2015] 星际战争解题报告

首先我们可以二分答案。

假设当前二分出来的答案是 $Ans$ ，那么我们考虑用网络流检验：

设武器为 $X$，第 $i$ 个武器的攻击力为 $B_i$；

设机器人为 $Y$，第 $i$ 个机器人的装甲为 $A_i$；

设 $Map[i][j]$ 表示第 $i$ 个机器人是否能攻击第 $j$ 号机器人。

设源为 $S$，汇为 $T$，现在考虑连边：

$S ightarrow X_i$，容量为 $Ans * B_i$；
$Y_i ightarrow T$，容量为 $A_i$；
$forall (i,j),Map[i][j]=1:X_i ightarrow Y_j$，容量为 $infty$

然后跑网络流，假设最大流为 $M$，那么看是否有：$M=sum A_i$。

如果是，那么说明当前答案是满足的，更新上界，否则更新下界。

毕竟 Gromah 太弱，只会做水题。

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 using namespace std;
  7 typedef long double LD;
  8 #define N 50 + 5
  9 #define M 100000 + 5
 10 #define INF 1e9
 11 #define eps 1e-9
 12  
 13 int n, m, S, T, sum, tot;
 14 int A[N], B[N];
 15 int Head[N << 1], q[N << 1], Dfn[N << 1];
 16 bool Map[N][N];
 17 LD l = 0.0, r;
 18  
 19 struct Edge
 20 {
 21     int next, node;
 22     LD flow;
 23 }h[M];
 24  
 25 inline void addedge(int u, int v, LD fl)
 26 {
 27     h[++ tot].next = Head[u], Head[u] = tot;
 28     h[tot].node = v, h[tot].flow = fl;
 29     h[++ tot].next = Head[v], Head[v] = tot;
 30     h[tot].node = u, h[tot].flow = 0;
 31 }
 32  
 33 inline bool BFS()
 34 {
 35     for (int i = S; i <= T; i ++)
 36         Dfn[i] = 0;
 37     int l = 1, r = 1;
 38     q[1] = S, Dfn[S] = 1;
 39     while (l <= r)
 40     {
 41         int z = q[l ++];
 42         for (int i = Head[z]; i; i = h[i].next)
 43         {
 44             int d = h[i].node;
 45             LD p = h[i].flow;
 46             if (p < eps || Dfn[d]) continue ;
 47             Dfn[d] = Dfn[z] + 1;
 48             q[++ r] = d;
 49             if (d == T) return 1;
 50         }
 51     }
 52     return 0;
 53 }
 54  
 55 inline LD dinic(int z, LD inflow)
 56 {
 57     if (z == T || inflow < eps) return inflow;
 58     LD ret = inflow, flow;
 59     for (int i = Head[z]; i; i = h[i].next)
 60     {
 61         int d = h[i].node;
 62         LD p = h[i].flow;
 63         if (Dfn[d] != Dfn[z] + 1) continue ;
 64         flow = dinic(d, min(p, ret));
 65         ret -= flow;
 66         h[i].flow -= flow, h[i ^ 1].flow += flow;
 67         if (ret < eps) return inflow;
 68     }
 69     if (fabs(inflow - ret) < eps) Dfn[z] = -1;
 70     return inflow - ret;
 71 }
 72  
 73 inline bool Judge(LD k)
 74 {
 75     tot = 1;
 76     for (int i = S; i <= T; i ++)
 77         Head[i] = 0;
 78     for (int i = 1; i <= m; i ++)
 79         addedge(S, i, k * B[i]);
 80     for (int i = 1; i <= n; i ++)
 81         addedge(i + m, T, A[i]);
 82     for (int i = 1; i <= m; i ++)
 83         for (int j = 1; j <= n; j ++)
 84             if (Map[i][j]) addedge(i, j + m, INF);
 85     LD res = 0.0;
 86     while (BFS())
 87         res += dinic(S, INF);  
 88     return fabs(res - sum) < eps;
 89 }
 90  
 91 int main()
 92 {
 93     #ifndef ONLINE_JUDGE
 94         freopen("3993.in", "r", stdin);
 95         freopen("3993.out", "w", stdout);
 96     #endif
 97      
 98     scanf("%d%d", &n, &m);
 99     S = 0, T = n + m + 1;
100     for (int i = 1; i <= n; i ++)
101     {
102         scanf("%d", A + i);
103         r += A[i];
104         sum += A[i];
105     }
106     for (int i = 1; i <= m; i ++)
107         scanf("%d", B + i);
108     for (int i = 1; i <= m; i ++)
109         for (int j = 1; j <= n; j ++)
110             scanf("%d", Map[i] + j);
111     while (l + 1e-4 < r)
112     {
113         LD mid = (l + r) / 2;
114         if (Judge(mid)) r = mid;
115             else l = mid;
116     }
117     printf("%.4lf
", (double) l);
118      
119     #ifndef ONLINE_JUDGE
120         fclose(stdin);
121         fclose(stdout);
122     #endif
123     return 0;
124 }

3993_Gromah

BZOJ 3993 [SDOI 2015] 星际战争 解题报告

BZOJ 3993 [SDOI 2015] 星际战争解题报告