BZOJ 3993: [SDOI2015]星际战争 October 26, 2016 ###Description 3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时，这个巨型机器人就被摧毁了。X军团有M个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭，他们急需下达更多的指令。为了这个目标，Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。 ###Input 第一行，两个整数，N、M。 第二行，N个整数，A1、A2…AN。 第三行，M个整数，B1、B2…BM。 接下来的M行，每行N个整数，这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人，为1表示第i个激光武器可以攻击第j个巨型机器人。 ###Output 一行，一个实数，表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10-3即视为正确。 ###Sample Input 2 2 3 10 4 6 0 1 1 1 ###Sample Output 1.300000 ###HINT 战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值； 接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。 对于全部的数据，1<=N, M<=50，1<=Ai<=105，1<=Bi<=1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人 ###Solution 考虑二分答案，假设当前答案为time，那么从源点到Bi连容量为time*Bi的边，从Ai到汇点连容量为Ai的边，Bi,Ai间连inf，跑最大流即可 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} #define mp(a,b) std::make_pair(a,b) #define pb push_back const int N=200,M=3000; struct edge { int to,ne; double w; }e[M*2+2]; int p[N+1],em=2,dep[N+1],q[N],qe,fa[N+1]; double fl[N+1]; bool vis[N+1]; inline void add(int a,int b,double w) { e[em].to=b,e[em].w=w,e[em].ne=p[a],p[a]=em++; e[em].to=a,e[em].w=0,e[em].ne=p[b],p[b]=em++; } bool dfs(int s,int t) { if(s==t)return 1; for(int j=p[s];j;j=e[j].ne) if(!vis[e[j].to]&&e[j].w&&dep[e[j].to]>dep[s]) { vis[e[j].to]=1; fl[e[j].to]=min(e[j].w,fl[s]); fa[e[j].to]=j^1; if(dfs(e[j].to,t))return 1; } return 0; } inline double dinic(int s,int t) { double flow=0; while(1) { memset(dep,0,sizeof(dep)); q[0]=s,qe=1,dep[s]=1; for(int i=0;i^qe;i++) { for(int j=p[q[i]];j;j=e[j].ne) if(!dep[e[j].to]&&e[j].w) { dep[e[j].to]=dep[q[i]]+1; q[qe++]=e[j].to; } } if(!dep[t])break; while(1) { memset(vis,0,sizeof(vis)); fl[s]=0x7fffffff; dfs(s,t); if(!vis[t])break; flow+=fl[t]; for(int i=t;i!=s;i=e[fa[i]].to) e[fa[i]].w+=fl[t],e[fa[i]^1].w-=fl[t]; } } return flow; } int n,m,a[50],b[50],atk[50][50]; inline bool judge(double time) { int s=n+m,t=n+m+1; memset(p,0,sizeof(p)); em=2; double s1=0,s2; for(int i=0;i<m;i++) add(s,i,time*b[i]); for(int i=0;i<n;i++) add(i+m,t,a[i]),s1+=a[i]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) if(atk[i][j]) add(i,j+m,1e20); s2=dinic(s,t); if(abs(s1-s2)<1e-4)return 1;else return 0; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%d",a+i); for(int i=0;i<m;i++) scanf("%d",b+i); for(int i=0;i<m;i++) for(int j=0;j<n;j++) { int k; scanf("%d",&k); atk[i][j]=k; } double l=0,r=1e4; while(r-l>1e-4) { if(judge((l+r)/2)) r=(l+r)/2; else l=(l+r)/2; } printf("%.6lf\n",r); } ```