P4048 [JSOI2010]冷冻波

出题人你tm搞笑呢,冰霜新星翻成冷冻波,而且tm就只能打一只小精灵???巫妖王都想来砍死你

首先要搞出每个巫妖能不能打到每一个小精灵,然后二分时间,就能算出每个巫妖可以打的次数,网络流check即可

但是你要搞出每个巫妖能不能打到每一个小精灵。。。贼jb麻烦,为此搜了N个公式才搞出来,我还是太菜了

#include<bits/stdc++.h>
#define il inline
#define vd void
#define sqr(x) ((x)*(x))
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
bool yes[201][201];
int X0[201],Y0[201],R[201],d[201];
int X1[201],Y1[201],X2[201],Y2[201],r2[201];
const int maxn=410,S=401,T=402,maxm=500000;
int fir[maxn],head[maxn],dis[maxm],nxt[maxm],w[maxm],id,dep[maxn];
il vd link(int a,int b,int c){
nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c;
nxt[++id]=fir[b],fir[b]=id,dis[id]=a,w[id]=0;
}
il bool BFS(){
static int que[maxn],hd,tl;
memset(dep,0,sizeof dep);
hd=tl=0;que[tl++]=S;
dep[S]=1;
while(hd^tl){
int x=que[hd++];
for(int i=fir[x];i;i=nxt[i])
if(w[i]&&!dep[dis[i]])dep[dis[i]]=dep[x]+1,que[tl++]=dis[i];
}
return dep[T];
}
il int Dinic(int x,int maxflow){
if(x==T)return maxflow;
int ret=0;
for(int&i=head[x];i;i=nxt[i])
if(w[i]&&dep[dis[i]]==dep[x]+1){
int d=Dinic(dis[i],std::min(w[i],maxflow-ret));
w[i]-=d,w[i^1]+=d,ret+=d;
if(ret==maxflow)break;
}
return ret;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("4048.in","r",stdin);
freopen("4048.out","w",stdout);
#endif
int n=gi(),m=gi(),t=gi();
for(int i=1;i<=n;++i)X0[i]=gi(),Y0[i]=gi(),R[i]=gi(),d[i]=gi();
for(int i=1;i<=m;++i)X1[i]=gi(),Y1[i]=gi();
for(int i=1;i<=t;++i)X2[i]=gi(),Y2[i]=gi(),r2[i]=gi();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(sqr(X0[i]-X1[j])+sqr(Y0[i]-Y1[j])<=R[i]*R[i]){
bool flg=1;
for(int k=1;k<=t;++k)
if(X0[i]==X1[j]){
if(abs(X0[i]-X2[k])>r2[k])continue;
double yy0=Y0[i],yy1=Y1[j];
if(yy0>yy1)std::swap(yy0,yy1);
if(yy0<=Y2[k]&&Y2[k]<=yy1){flg=0;break;}
}else{
double k0=1.0*(Y0[i]-Y1[j])/(X0[i]-X1[j]),b0=Y0[i]-X0[i]*k0;
double dist1=fabs(k0*X2[k]-Y2[k]+b0)/sqrt(1+k0*k0);
double xx=X2[k]+sin(atan(-1/k)),xx0=X0[i],xx1=X1[j];
if(xx0>xx1)std::swap(xx0,xx1);
if(dist1<=r2[k]&&xx0<=xx&&xx<=xx1){flg=0;break;}
}
if(flg)yes[i][j]=1;
}
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j)if(yes[j][i])goto GG;
return puts("-1"),0;
GG:;
}
int l=0,r=20000*m,mid;
while(l<r){
mid=((l+r)>>1);
memset(fir,0,sizeof fir);id=1;
for(int i=1;i<=n;++i)link(S,i,mid/d[i]+1);
for(int i=1;i<=m;++i)link(i+n,T,1);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(yes[i][j])link(i,j+n,1);
int tot=0;while(BFS())memcpy(head,fir,sizeof head),tot+=Dinic(S,1e9);
if(tot==m)r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
上一篇:BZOJ1822 [JSOI2010]Frozen Nova 冷冻波 二分+最大流


下一篇:获取本机IP