bzoj 3993 星际战争
2024-09-10 14:22:32
题目大意:
X军团和Y军团正在激烈地作战 在战斗的某一阶段,Y军团一共派遣了N个巨型机器人进攻X军团的阵地,其中第i个巨型机器人的装甲值为Ai
当一个巨型机器人的装甲值减少到0或者以下时,这个巨型机器人就被摧毁了
X军团有M个激光武器,其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值
激光武器的攻击是连续的。这种激光武器非常奇怪,一个激光武器只能攻击一些特定的敌人
Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁
思路:
建图还是比较好想的
但是答案需要二分,然后用最大流判断
连边的时候
每个武器和超级源连一条时间(二分得到)* Bi 的边
每个武器和它可以消灭的机器人连一条流量为这个武器到源点的流量的边
每个机器人和超级汇连一条流量 Ai 的边
每次二分之后判断最大流是不是等于Ai之和即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ll long long
#define inf 2139062143
#define MAXN 120
#define eps 1e-4
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) x=x*+ch-'',ch=getchar();
return x*f;
}
int n,m,a[MAXN],b[MAXN],mp[MAXN][MAXN],sum;
struct Dinic
{
int cnt,s,t,nxt[MAXN*MAXN],fst[MAXN],to[MAXN*MAXN],cur[MAXN*MAXN];
double val[MAXN*MAXN];
int vis[MAXN],q[MAXN],dep[MAXN],l,r,tot;
void mem() {cnt=;memset(fst,0xff,sizeof(fst));}
void add(int u,int v,double w) {nxt[cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt++]=w;}
void build(double x)
{
mem();
for(int i=;i<=m;i++) add(s,i,x*b[i]),add(i,s,);
for(int i=;i<=n;i++) add(i+m,t,a[i]),add(t,m+i,);
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
if(mp[i][j]) add(i,m+j,x*b[i]),add(m+j,i,);
}
int bfs()
{
memset(dep,0xff,sizeof(dep));
l=r=,q[r]=t,vis[t]=++tot;
while(l<=r)
{
int x=q[l++];
for(int i=fst[x];i!=-;i=nxt[i])
{
if(val[i^]&&vis[to[i]]!=tot)
{
vis[to[i]]=tot,dep[to[i]]=dep[x]+,q[++r]=to[i];
if(to[i]==s) return ;
}
}
}
return vis[s]==tot;
}
double dfs(int x,double a)
{
if(x==t||!a) return a;
double flow=,f;
for(int& i=cur[x];i!=-;i=nxt[i])
if(val[i]&&dep[to[i]]==dep[x]-&&(f=dfs(to[i],min(val[i],a))))
{
val[i]-=f,val[i^]+=f,flow+=f,a-=f;
if(!a) break;
}
return flow;
}
double solve()
{
double ans=,f;
while(bfs())
{
for(int i=;i<=n+m+;i++) cur[i]=fst[i];
while(f=dfs(s,inf)) ans+=f;
}
return ans;
}
}D;
int main()
{
n=read(),m=read();
for(int i=;i<=n;i++) a[i]=read(),sum+=a[i];
for(int i=;i<=m;i++) b[i]=read();
for(int i=;i<=m;i++)
for(int j=;j<=n;j++) mp[i][j]=read();
D.s=,D.t=n+m+;
double l=,r=sum,mid;
while(r-l>=eps)
{
mid=(l+r)/;
D.build(mid);
if(D.solve()==sum) r=mid;
else l=mid;
}
printf("%lf",l);
}
最新文章
- X509 证书生成
- c++从文件中读取特定字符串问题的总结
- JSch - Java实现的SFTP(文件上传详解篇)
- Java中的super与this解析
- IOS开发UI篇之tableView 的用法详解
- POJ 1733 Parity game (并查集)
- Z-Stack学习笔记
- 不使用var定义变量和使用var的区别
- caffe之(五)loss层
- Selenium+Java+TestNG环境配置
- 小米路由器mini建FTP
- 【常用小命令】解决windows下有些文件文件名识别不了导致删除不了的问题
- 201521123080《Java程序设计》第9周学习总结
- nexus3 添加第三方本地文件jar到仓库
- angular4.0如何引入外部插件1:import方案
- python 爬取B站视频弹幕信息
- Java中异常的处理以及自定义异常,抛出异常到方法调用栈底层
- python安装tesseract
- 再战android-语音识别2(修改配置)
- webform(复合控件)