出題人你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_JUDGEfreopen("4048.in","r",stdin);freopen("4048.out","w",stdout); #endifint 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; }

轉載于:https://www.cnblogs.com/xzz_233/p/9819285.html

總結

以上是生活随笔為你收集整理的P4048 [JSOI2010]冷冻波的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。