文章目录题目分析代码
题目
Description3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了NNN个巨型机器人进攻X军团的阵地，其中第iii个巨型机器人的装甲值为AiA_iAi。当一个巨型机器人的装甲值减少到000或者以下时，这个巨型机器人就被摧毁了。X团有MMM个激光武器，其中第iii个激光武器每秒可以削减一个巨型机器人BiB_iBi的装甲值。激武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭，他们急需下达更多的指令。为了这个目标，Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。
Input第一行，两个整数，NNN、MMM。第二行，NNN个整数，A1A_1A1、A2A_2A2、…、ANA_NAN。第三行，MMM个整数，B1B_1B1、B2B_2B2、…、BMB_MBM。接下来的MMM行，每行NNN个整数，这些整数均为0或者1。这部分中的第iii行的第jjj个整数为0表示第iii个激光武器不可以攻击第jjj个巨型机器人，为1表示第iii个激光武器可以攻击第jjj个巨型机器人。
Output一行，一个实数，表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10−310^{-3}10−3即视为正确。
SampleInput22310460111
SampleOutput1.300000
Hint战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值；接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。
Dataconstraint对于全部的数据，1≤N,M≤501\leqN,M\leq501≤N,M≤50，1≤Ai≤1051\leqA_i\leq10^51≤Ai≤105，1≤Bi≤10001\leqB_i\leq10001≤Bi≤1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人。
分析
看了提示才发现可以分配小数时间给每个敌人。二分时间ttt，注意精度问题。每个武器是独立的，把源点向每个武器连流量为ttt的边，这样就控制了它的攻击时间；每个武器iii向它能攻击的机器人jjj连流量为+∞+\infty+∞的边；每个机器人jjj向汇点连流量为BjAi\dfrac{B_j}{A_i}AiBj（即打爆它的时间）。跑Dinic就好了。
代码#include<cmath>#include<queue>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;intread(){intx=0;boolf=0;charc=getchar();while(c<'0'||c>'9')f|=c=='-',c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();returnf?-x:x;}#defineMAXN100#defineINF1e7#defineeps1e-6intN,M;intA[MAXN+5],B[MAXN+5];boolP[MAXN+5][MAXN+5];structEdge{doublew;intv,Next;Edge(){}inlineEdge(intx,doubley,intz){v=x,w=y,Next=z;}}E[MAXN*MAXN+5];intecnt,Adj[MAXN*2+5];inlinevoidAddEdge(intu,intv,doublew){E[ecnt]=Edge(v,w,Adj[u]),Adj[u]=ecnt++;E[ecnt]=Edge(u,0,Adj[v]),Adj[v]=ecnt++;}intCur[MAXN*2+5];intDist[MAXN*2+5];boolbfs(intS,intT){for(inti=0;i<=N+M+1;i++)Cur[i]=Adj[i],Dist[i]=INF;queue<int>Q;Dist[S]=0,Q.push(S);while(!Q.empty()){intu=Q.front();Q.pop();for(inti=Adj[u];i!=-1;i=E[i].Next){intv=E[i].v;if(abs(E[i].w)>eps&&Dist[v]>Dist[u]+1){Dist[v]=Dist[u]+1;Q.push(v);}}}returnDist[T]<INF;}doubledfs(intu,intT,doubleMin){if(abs(Min)<=eps||u==T)returnMin;doubleNow=0,Rest=Min;for(inti=Cur[u];i!=-1;i=E[i].Next){Cur[u]=i;intv=E[i].v;if(Dist[v]==Dist[u]+1){if(abs(Now=dfs(v,T,min(Rest,E[i].w)))>eps){Rest-=Now;E[i].w-=Now;E[i^1].w+=Now;if(abs(Rest)<eps)break;}}}returnMin-Rest;}doubleDinic(intS,intT){doubleMaxFlow=0;while(bfs(S,T))MaxFlow+=dfs(S,T,INF);returnMaxFlow;}intSum;boolCheck(doubleexpt){//暴力重建ecnt=0;memset(Adj,-1,sizeofAdj);for(inti=1;i<=M;i++)for(intj=1;j<=N;j++)if(P[i][j])AddEdge(i,j+M,INF);for(inti=1;i<=M;i++)AddEdge(0,i,expt*B[i]);for(inti=1;i<=N;i++)AddEdge(i+M,N+M+1,A[i]);returnabs(Dinic(0,N+M+1)-Sum)<=eps;}intmain(){N=read(),M=read();for(inti=1;i<=N;i++)Sum+=(A[i]=read());for(inti=1;i<=M;i++)B[i]=read();for(inti=1;i<=M;i++)for(intj=1;j<=N;j++)P[i][j]=read();doubleLeft=0,Right=INF;for(inti=1;i<=100;i++){doubleMid=(Left+Right)/2;if(Check(Mid))Right=Mid;elseLeft=Mid;}printf("%f",Right);return0;}
