BZOJ 3993 [SDOI2015]星际战争 二分+最大流

题意: 有n个怪兽，m个武器，，每个武器能打哪些怪兽的关系已给出，每个武器在1s内可以打多少血量已给出，每个怪兽有多少血量已给出。 求怪兽团灭的最小时间。 解析: 同样是一道答案存在单调性的题目。 所以我们可以考虑二分答案后，每一次重新构建一次图。 修改的地方其实就是原点到每个武器的流量（即二分的答案时间内该武器最多能打血）以及将上一次跑过的图复原。 最后判断最大流是否等于怪兽总血量即可。 注意浮点数相等判断。 代码:

;int n,m;int head[3*N],cnt;double sum;struct node{int from,to,next;double val;}edge[(N*N)<<2];double b[N];void init(){memset(head,-1,sizeof(head));}void edgeadd(int from,int to,double val){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].val=val;edge[cnt].next=head[from];head[from]=cnt++;}double dis[N*3];int dep[N*3];int S,T;int bfs(){memset(dep,0,sizeof(dep));queue<int>q;q.push(S);dep[S]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){int to=edge[i].to;if(dep[to]!=0||fabs(edge[i].val)<eps)continue;dep[to]=dep[u]+1;q.push(to);}}return dep[T]?1:0;}double dfs(int now,double max_vale){double ret=0;if(now==T)return max_vale;for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;if(dep[to]!=dep[now]+1||fabs(edge[i].val)<eps)continue;double tmp=dfs(to,min(max_vale-ret,edge[i].val));ret+=tmp;edge[i].val-=tmp;edge[i^1].val+=tmp;if(fabs(ret-max_vale)<eps)return max_vale;}return ret;}bool check(double mid){for(int i=0;i<cnt;i+=2)edge[i].val+=edge[i^1].val,edge[i^1].val=0;for(int i=head[S];i!=-1;i=edge[i].next)edge[i].val=b[edge[i].to-n]*mid;double ret=0;while(bfs()){while(double t=dfs(S,INF)){ret+=t;}}if(fabs(ret-sum)<eps)return 1;return 0;}int main(){init();scanf(“%d%d”,&n,&m);S=0,T=n+m+1;for(int i=1;i<=n;i++){int x;scanf(“%d”,&x);edgeadd(i,T,x);edgeadd(T,i,0);sum+=x;}for(int i=1;i<=m;i++){scanf(“%lf”,&b[i]);edgeadd(S,n+i,INF);edgeadd(n+i,S,0);}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){int jd;scanf(“%d”,&jd);if(jd){edgeadd(n+i,j,INF);edgeadd(j,n+i,0);}}}double l=0,r=INF;double ans=l;while(r-l>eps){double mid=(l+r)/2.0;if(check(mid))ans=mid,r=mid;else l=mid;}printf(“%lf\n”,ans);}

如果你曾歌颂黎明，那么也请你拥抱黑夜