BZOJ 3993 [SDOI2015]星际战争 二分+最大流
来源：程序员人生 发布时间：2016-05-31 16:35:45 阅读次数：2318次
题意:
有n个怪兽，m个武器，每一个武器能打哪些怪兽的关系已给出，每一个武器在1s内可以打多少血量已给出，每一个怪兽有多少血量已给出。
求怪兽团灭的最小时间。
解析:
一样是1道答案存在单调性的题目。
所以我们可以斟酌2分答案后，每次重新构建1次图。
修改的地方其实就是原点到每一个武器的流量（即2分的答案时间内该武器最多能打血）和将上1次跑过的图复原。
最后判断最大流是不是等于怪兽总血量便可。
注意浮点数相等判断。
代码:
#include #include #include #include #include #include #define N 55 #define INF 0x3f3f3f3f #define eps 1e⑻ using namespace std; 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)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)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)return max_vale;
} return ret;
} bool check(double mid)
{ for(int i=0;i2)
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)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
",ans);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
