Time Limit: 1000 ms Memory Limit: 128 MB
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
【样例说明1】
战斗开始后的前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
如果答案是$t$，那么最大流的连边方法是：源点向每一门炮$i$连一条容量$B_i*t$的边，炮向对应机器人连容量正无穷的边，机器人向汇点连容量$A_i$的边。
这个模型的关键在于，如果时间$t$定下来，即每一门炮的输出量固定，那么只需用最大流分配一次，看一看每一个机器人是否被流满所需值$A_i$，即最大流是不是$\sum A_i$，就可以判断这一个时间内满不满足要求。因为如果最大流是$\sum A_i$，必定存在一种激光炮的合作方案能在$t$内消灭机器人。
那么直接对$t$二分答案来跑最大流就好啦。
记得用$eps$判断。
#include <cstdio>
#include <queue>
using namespace std;
const double INF=1e10,eps=1e-
5;
int n,m,all,S,T,can[
55][
55],a[
55],b[
55],sum;
int h[
110],tot;
int dis[
110],cur[
110];
struct Edge{
int v,next;
double f;}g[
6010];
queue<
int>
q;
inline double min(
double x,
double y){
return x<y?
x:y;}
inline double abs(
double x){
return x<
0?-
x:x;}
inline void addEdge(
int u,
int v,
double f){
g[++tot].v=v; g[tot].f=f; g[tot].next=h[u]; h[u]=
tot;
g[++tot].v=u; g[tot].f=
0; g[tot].next=h[v]; h[v]=
tot;
}
bool bfs(){
while(!
q.empty()) q.pop();
q.push(S);
for(
int i=
1;i<=all;i++) dis[i]=-
1;
dis[S]=
0;
while(!
q.empty()){
int u=
q.front(); q.pop();
for(
int i=h[u],v;i;i=
g[i].next)
if(g[i].f>eps&&dis[v=g[i].v]==-
1){
dis[v]=dis[u]+
1;
if(v==T)
return true;
q.push(v);
}
}
return dis[T]!=-
1;
}
double dfs(
int u,
double delta){
if(u==T)
return delta;
double get,ret=
0;
for(
int i=cur[u],v;i&&delta>eps;i=
g[i].next)
if(g[i].f>eps&&dis[v=g[i].v]==dis[u]+
1){
get=
dfs(v,min(delta,g[i].f));
g[i].f-=
get;
g[i^
1].f+=
get;
if(g[i].f>eps) cur[u]=
i;
delta-=
get;
ret+=
get;
}
if(ret<eps) dis[u]=-
1;
return ret;
}
double dinic(){
double ret=
0;
while(bfs()){
for(
int i=
1;i<=all;i++) cur[i]=
h[i];
ret+=
dfs(S,INF);
}
return ret;
}
void buildGraph(
double t){
tot=
1;
for(
int i=
1;i<=all;i++) h[i]=
0;
for(
int i=
1;i<=m;i++
)
addEdge(S,i,t*
b[i]);
for(
int i=
1;i<=m;i++
)
for(
int j=
1;j<=n;j++
)
if(can[i][j])
addEdge(i,m+
j,INF);
for(
int i=
1;i<=n;i++
)
addEdge(m+
i,T,a[i]);
}
int main(){
scanf("%d%d",&n,&
m);
all=n+m+
2; S=n+m+
1; T=n+m+
2;
for(
int i=
1;i<=n;i++) scanf(
"%d",&a[i]),sum+=
a[i];
for(
int i=
1;i<=m;i++) scanf(
"%d",&
b[i]);
for(
int i=
1;i<=m;i++
)
for(
int j=
1;j<=n;j++) scanf(
"%d",&
can[i][j]);
double l=
0,r=
1000000000,mid,ans;
while(l+eps<
r){
mid=(l+r)/
2;
buildGraph(mid);
ans=
dinic();
if(abs(sum-ans)<eps) r=
mid;
else l=
mid;
}
printf("%.8lf\n",l);
return 0;
}
奇妙代码
转载于:https://www.cnblogs.com/RogerDTZ/p/8012482.html
