3993: [SDOI2015]星际战争
题目:传送门
题解:
洛谷AC了,但是因为bzoj的spj有问题所以暂时没A
一道老题目了,二分时间然后网络流判断。
每次st-->武器连时间*攻击力
武器-->机器人 流量无限
机器人-->ed 流量为血量值
精度有点gou...
代码:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define eps 1e-7
#define inf 999999999.0
using namespace std;
struct node
{
int x,y,next,other;
double c;
}a[];int len,last[];
void ins(int x,int y,double c)
{
int k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int st,ed,n,m,head,tail;
int list[],h[];
bool bt_h()
{
memset(h,,sizeof(h));h[st]=;
list[]=st;head=;tail=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(!h[y] && a[k].c>)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed])return true;
return false;
}
double find_flow(int x,double flow)
{
if(x==ed)return flow;
double s=,t;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]+ && a[k].c> && s<flow)
{
s+=t=find_flow(y,min(a[k].c,flow-s));
a[k].c-=t;a[a[k].other].c+=t;
}
}
if(s==)h[x]=;
return s;
}
double A[],B[];
int map[][];
bool check(double x)
{
double sum=0.0,ans=0.0;
len=;memset(last,,sizeof(last));
for(int i=;i<=m;i++)ins(st,i,x*B[i]);
for(int i=;i<=m;i++)for(int j=;j<=n;j++)if(map[i][j]==)ins(i,j+m,inf);
for(int i=;i<=n;i++)ins(i+m,ed,A[i]),sum+=A[i];
while(bt_h())ans+=find_flow(st,inf);
if(abs(ans-sum)<=eps)return true;
return false;
}
int main()
{
scanf("%d%d",&n,&m);for(int i=;i<=n;i++)scanf("%lf",&A[i]);for(int i=;i<=m;i++)scanf("%lf",&B[i]);
st=n+m+,ed=st+;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
scanf("%d",&map[i][j]);
double l=0.0,r=10000000.0,ans=0.0;
while(l<=r)
{
double mid=(l+r)/;
if(check(mid))ans=mid,r=mid-eps;
else l=mid+eps;
}
printf("%.6lf\n",ans);
return ;
}