題解

直接二分然后建圖跑網絡流看看是否合法即可

就是源點向每個激光武器連一條二分到的時間×激光武器每秒攻擊值的邊
每個激光武器向能攻擊的裝甲連一條邊
每個裝甲向匯點連一條裝甲值的邊

代碼

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define pdi pair<db,int> #define mp make_pair #define pb push_back #define enter putchar('\n') #define space putchar(' ') #define eps 1e-8 #define mo 974711 #define MAXN 30005 //#define ivorysi using namespace std; typedef long long int64; typedef double db; template<class T> void read(T &res) {res = 0;char c = getchar();T f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } int N,M; int A[55],B[55],g[55][55]; struct node {int to,next;db cap; }E[1000005]; int sumE,head[205],cur[205],S,T,lev[205]; db all = 0; void add(int u,int v,db c) {E[++sumE].to = v;E[sumE].cap = c;E[sumE].next = head[u];head[u] = sumE; } void addtwo(int u,int v,db c) {add(u,v,c);add(v,u,0); } void Init() {read(N);read(M);for(int i = 1 ; i <= N ; ++i) {read(A[i]);all += A[i];}for(int i = 1 ; i <= M ; ++i) read(B[i]);for(int i = 1 ; i <= M ; ++i) {for(int j = 1 ; j <= N ; ++j) {read(g[i][j]);}} } bool BFS() {static int que[205],ql,qr;sumE = 0;for(int i = S ; i <= T ; ++i) {cur[i] = head[i];lev[i] = -1;}que[ql = qr = 1] = S;lev[S] = 0;while(ql <= qr) {int u = que[ql++];for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(E[i].cap > 0 && lev[v] == -1) {lev[v] = lev[u] + 1;que[++qr] = v;if(v == T) return true;}}}return false; } db dfs(int u,db aug) {if(u == T) return aug;db flow = 0;for(int &i = cur[u] ; i ; i = E[i].next) {if(E[i].cap > 0) {int e = i,v = E[i].to;if(lev[v] > lev[u]) {db t = dfs(v,min(E[e].cap,aug - flow));flow += t;E[e].cap -= t;E[e ^ 1].cap += t;if(flow == aug) break;}}}if(flow != aug) lev[u] = -1;return flow; } bool check(db mid) {sumE = 1;memset(head,0,sizeof(head));S = 1,T = 1 + M + N + 1;for(int i = 1 ; i <= M ; ++i) {addtwo(S,S + i,mid * B[i]);}for(int i = 1 ; i <= N ; ++i) {addtwo(1 + M + i,T,A[i]);}for(int i = 1 ; i <= M ; ++i) {for(int j = 1 ; j <= N ; ++j) {if(g[i][j]) addtwo(1 + i,1 + M + j,1000000000);}}db res = 0;while(BFS()) {res += dfs(S,1000000000);}if(res < all) return false;return true; } void Solve() {db L = 0,R = 100000 * N;int cnt = 60;while(cnt--) {db mid = (L + R) / 2;if(check(mid)) R = mid;else L = mid;}printf("%.3lf\n",L); } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifInit();Solve(); }

轉載于:https://www.cnblogs.com/ivorysi/p/10143057.html

總結

以上是生活随笔為你收集整理的【LOJ】#2184. 「SDOI2015」星际战争的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。