题解 P3324 【[SDOI2015]星际战争】
一道网络流的题目，建图非常明显，从S往激光连一条边权为inf的边，激光往机器人连边权为inf的边，机器人往T连边权为bi的边。
但是这道题的要求是算最小时间，对于一个激光武器，从S到激光武器的边中的流量就是这个激光武器的输出，时间就是流量/ai。
于是这道题转化成了给一个网络流图，对于指定的边，要求在最大流的情况下这些边中的最大流量与一个定值的比最小。
于是我们可以二分这个比值，先从S往激光连inf的边，然后求最大流，然后开始二分比值t，S到激光的边的流量变为t*ai，然后最大流检测是否合法。
这道题精度要求是1e-3,可以不用double2分，把所有的流量全部乘1000，二分到整数即可。
二分的思路来自SDOI2013费用流。
代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int inf=1e9+7;
const long long longinf=1ll<<60;
#define min(a,b) a<b?a:b
int head[205],nxt[200005],point[200005],sum;
long long remain[200005];
int deep[205],nowedge[205];
queue<int>q;
int n,m,a[205],b[205],attack[205][205];
long long maxans,l,r,mid;
void add(int x,int y,long long flow)
{
++sum;nxt[sum]=head[x];head[x]=sum;point[sum]=y;remain[sum]=flow;
++sum;nxt[sum]=head[y];head[y]=sum;point[sum]=x;remain[sum]=0;
}
int bfs(int s,int t)
{
memset(deep,127,sizeof(deep));
for(int i=0;i<=n+m+1;i++)
nowedge[i]=head[i];
deep[s]=0;
q.push(s);
while(!q.empty())
{
int now=q.front();q.pop();
for(int tmp=head[now];tmp!=-1;tmp=nxt[tmp])
{
int u=point[tmp];
if(deep[u]>deep[now]+1&&remain[tmp])
{
deep[u]=deep[now]+1;
q.push(u);
}
}
}
return deep[t]<inf;
}
long long dfs(int x,int t,long long limit)
{
if(x==t||!limit) return limit;
long long flow=0,f;
for(int tmp=nowedge[x];tmp!=-1;tmp=nxt[tmp])
{
nowedge[x]=tmp;
int u=point[tmp];
if(deep[u]==deep[x]+1&&(f=dfs(u,t,min(remain[tmp],limit))))
{
flow+=f;
remain[tmp]-=f;
remain[tmp^1]+=f;
limit-=f;
}
}
return flow;
}
long long dinic(int s,int t)
{
long long ans=0;
while(bfs(s,t))
ans+=dfs(s,t,longinf);
return ans;
}
int check(long long x)
{
memset(nxt,-1,sizeof(nxt));
memset(head,-1,sizeof(head));
sum=-1;
for(int i=1;i<=n;i++)
add(i+m,m+n+1,a[i]*10000);
for(int i=1;i<=m;i++)
{
add(0,i,b[i]*x);
for(int j=1;j<=n;j++)
if(attack[i][j])
add(i,j+m,longinf);
}
long long checkans=dinic(0,m+n+1);
return checkans==maxans;
}
int main()
{
memset(nxt,-1,sizeof(nxt));
memset(head,-1,sizeof(head));
sum=-1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),add(i+m,m+n+1,a[i]*10000);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]),add(0,i,longinf);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&attack[i][j]);
if(attack[i][j])
add(i,j+m,longinf);
}
maxans=dinic(0,n+m+1);
int l=1,r=1000000000;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid))
r=mid-1;
else
l=mid+1;
}
printf("%.4lf",(r+1)*1.0/10000);
}