【LOJ】#2184. 「SDOI2015」星際戰爭

題解

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

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

代碼

#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();
}