P4048 [JSOI2010]冷冻波

时间：2022-01-23 20:06:58

出题人你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;

}

相关文章