考虑网络流，二分时间，源点向巫妖连流量为攻击次数的边，把每个巫妖向他能打的小精灵连一条流量为一的边，每个小精灵向汇点连一条边。
预处理每个小精灵能被那些巫妖打，这道题好像视线与树相切也算能打（雾。
#include<cmath>#include<queue>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=1e3+100,maxm=1e6+100,inf=0x7fffffff;struct Point{ ???double x,y; ???Point(double xx=0,double yy=0){ ???????x=xx,y=yy; ???}}tre[maxn],a[maxn],b[maxn];struct Vector{ ???double x,y; ???Vector(double xx=0,double yy=0){ ???????x=xx,y=yy; ???}};struct Grafh{ ???int v[maxm],w[maxm],nex[maxm],head[maxn],num; ???void add(int x,int y,int z){ ???????v[++num]=y; ???????w[num]=z; ???????nex[num]=head[x]; ???????head[x]=num; ???????v[++num]=x; ???????w[num]=0; ???????nex[num]=head[y]; ???????head[y]=num; ???} ???void clean(){ ???????memset(head,0,sizeof(head)); ???????num=1; ???} ???Grafh(){num=1;}}g,h;int dcmp(double x){return fabs(x)<1e-9?0:(x>0?1:-1);}Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}double dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}double len(Vector a){return sqrt(dot(a,a));}double dists(Point p,Point a,Point b){ ???Vector v1=b-a,v2=p-a,v3=p-b; ???if(dcmp(dot(v1,v2))<=0) return len(v2); ???else if(dcmp(dot(v1,v3))>=0) return len(v3); ???return fabs(v1*v2/len(v1));}int n,m,p;int cc[maxn],s,t;int cur[maxn],tim[maxn];double ar[maxn],tr[maxn];queue<int>q;bool bfs(){ ???memset(cc,0,sizeof(cc)); ???cc[s]=1; ???q.push(s); ???while(!q.empty()){ ???????int x=q.front(); ???????q.pop(); ???????for(int i=h.head[x];i;i=h.nex[i]) ???????????if(h.w[i]&&!cc[h.v[i]]) ???????????????cc[h.v[i]]=cc[x]+1,q.push(h.v[i]); ???} ???return cc[t];}int dfs(int x,int ll){ ???if(x==t) return ll; ???for(int &i=cur[x];i;i=h.nex[i]) ???????if(h.w[i]&&cc[h.v[i]]==cc[x]+1){ ???????????int pp=dfs(h.v[i],ll>h.w[i]?h.w[i]:ll); ???????????if(pp){ ???????????????h.w[i]-=pp; ???????????????h.w[i^1]+=pp; ???????????????return pp; ???????????} ???????} ???return 0;}int dinic(){ ???int maxl=0,ll; ???while(bfs()){ ???????memcpy(cur,h.head,sizeof(cur)); ???????while(ll=dfs(s,inf)) ???????????maxl+=ll; ???} ???return maxl;}bool getdist(){ ???s=0,t=n+m+1; ???for(int i=1;i<=m;i++){ ???????bool cz=0; ???????for(int j=1;j<=n;j++) ???????????if(dcmp(len(a[j]-b[i])-ar[j])<=0){ ???????????????bool ok=1; ???????????????for(int k=1;k<=p;k++) ???????????????????if(dcmp(dists(tre[k],b[i],a[j])-tr[k])<0){ ???????????????????????ok=0; ???????????????????????break; ???????????????????} ???????????????if(ok){ ???????????????????g.add(j,i+n,inf); ???????????????????cz=1; ???????????????} ???????????} ???????if(!cz){ ???????????printf("-1\n"); ???????????return 1; ???????} ???} ???for(int i=1;i<=m;i++) ???????g.add(i+n,t,1); ???return 0;}bool check(int x){ ???h=g; ???for(int i=1;i<=n;i++) ???????h.add(s,i,x/tim[i]+1); ???if(dinic()==m) return 1; ???return 0;}void work(){ ???int l=0,r=4000001,mid,ans=0; ???while(l<r){ ???????mid=l+r>>1; ???????if(check(mid)) ???????????ans=mid,r=mid; ???????else ???????????l=mid+1; ???} ???printf("%d\n",ans);}int main(){ ???scanf("%d%d%d",&n,&m,&p); ???for(int i=1;i<=n;i++) ???????scanf("%lf%lf%lf%d",&a[i].x,&a[i].y,&ar[i],&tim[i]); ???for(int i=1;i<=m;i++) ???????scanf("%lf%lf",&b[i].x,&b[i].y); ???for(int i=1;i<=p;i++) ???????scanf("%lf%lf%lf",&tre[i].x,&tre[i].y,&tr[i]); ???if(getdist()) return 0; ???work(); ???return 0;}Luogu-4048 [JSOI2010]冷冻波
原文地址：https://www.cnblogs.com/nianheng/p/10010054.html