P4048 [JSOI2010]冷冻波 题解

· · 题解

首先很好想到我们应该预处理出来每一个巫妖王能攻击到的精灵。

那么这就是一个几何题。

对于每一组精灵与巫妖王，设巫妖王坐标为 (x_1,y_1)，精灵坐标为 (x_2,y_2)。不考虑树的影响，若巫妖王要看到精灵，那么得满足：

(x_1-x_2)^2+(y_1-y_2)^2\le r^2

用勾股定理或是两点间距离公式可以推出。

那么现在有了树的影响，对于每一棵树，我们都得计算它是否会遮挡视野。

如果一棵树会遮挡视野，当且仅当树经过了精灵与巫妖王的连线。

可以利用解析式求解。

精灵与巫妖王的连线斜率为：k_1=\frac{y_1-y_2}{x_1-x_2}。

代入直线解析式 y=k_1x+b_1 得截距。

&y=\frac{y_1-y_2}{x_1-x_2}x+b_1\\ &b_1=y-\frac{y_1-y_2}{x_1-x_2}x \end{aligned}

得到解析式后要求树是否会挡路，那么就要求树到这儿的最短距离，即垂线段长度，这里依然用的解析法。

垂线段斜率：k_2=-\frac{1}{k_1}

垂线段截距：

&y=k_2x+b_2\\ &b_2=y-k_2x\\ &b_2=y+\frac{x}{k_1}\\ &b_2=y+\frac{x}{\frac{y_1-y_2}{x_1-x_2}}\\ &b_2=y+\frac{x\times(x_1-x_2)}{y_1-y_2} \end{aligned}

最后解交点坐标 (x_3,y_3)：

&k_1x_3+b_1=k_2x_3+b_2\\ &(k_1-k_2)x_3=b_2-b_1\\ &x_3=\frac{b_2-b_1}{k_1-k_2}\\ &y_3=k_1x_3+b_1\\ &y_3=k_1\times \frac{b_2-b_1}{k_1-k_2}+b_1 \end{aligned}

如果树会挡路当且仅当交点在线段上，且交点距离树的距离小于半径 r_2。

若交点在线段上，那么 x_3\ge\min(x_1,x_2) 且 x_3\le\max(x_1,x_2)

若距离小于半径，设树的坐标为 (x_4,y_4)。

那么 \sqrt{(x_4-x_3)^2+(y_4-y_3)^2}<r_2

由于此时坐标为浮点数，可以利用开方解决。

预处理做完后，就开始求时间花费了。

如果抛开冷却不谈，而是求本题有无解，仅仅是问对于每一个精灵是否能有一个巫妖王与之匹配。

如果再限制每个巫妖王施法次数，就是一个最大流问题。

连接源点与每一个巫妖王，边权是该巫妖王可攻击次数。再连接每一个巫妖王与可以攻击到的精灵，边权赋为 1，因为一个巫妖王只能攻击一次相同的精灵。最后连接每个精灵与汇点，边权为 1，因为每个精灵只能死一次。最后跑最大流即可得出是否有解。

现在有了冷却时间，实际上在一定时间 time 内第 i 个巫妖王可攻击次数为 time\div t_i+1。

而本题答案满足单调性，所以可以二分时答案，找到每个巫妖王的攻击次数，每一次跑一个最大流，就可以得到答案了。

约等于二分图匹配所以复杂度为 O((n+m)\times\sqrt {n+m})。

预处理复杂度为 O(nmk)。

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int N=505;
int n,m,k,num[N],dep[N],vis[N];
struct node
{
    int to,data;
};
vector<node>t[N];
vector<int>p[N];
struct wyw
{
    int x,y,r,t;
}a[N];
struct xjl
{
    int x,y;
}b[N];
struct tree
{
    int x,y,r;
}c[N];
inline int tabs(int x)
{
    return x>0?x:-x;
}
bool bfs()
{
    memset(dep,0,sizeof(dep));
    queue<int>q;
    q.push(0);
    dep[0]=1;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        int len=t[x].size();
        for(int i=0;i<len;i++)
        {
            if(t[x][i].data&&!dep[t[x][i].to])dep[t[x][i].to]=dep[x]+1,q.push(t[x][i].to);
        }
    }
    if(dep[n+m+1])return true;
    return false;
}
int dfs(int x,int num)
{
    if(x==n+m+1)return num;
    if(vis[x])return 0;
    vis[x]=1;
    int len=t[x].size();
    for(int i=0;i<len;i++)
    {
        if(t[x][i].data&&dep[t[x][i].to]==dep[x]+1)
        {
            int res=dfs(t[x][i].to,min(num,t[x][i].data));
            if(res)
            {
                t[x][i].data-=res;
                t[t[x][i].to][p[x][i]].data+=res;
                return res;
            }
        }
    }
    return 0;
}
int main()
{
    //freopen("cold.in","r",stdin);
    //freopen("cold.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].r,&a[i].t),num[i]=-a[i].t;
    for(int i=1;i<=m;i++)scanf("%d%d",&b[i].x,&b[i].y);
    for(int i=1;i<=k;i++)scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y)>a[i].r*a[i].r)continue;
            bool flag=1;
            for(int q=1;q<=k;q++)
            {
                double xielv=1.0*(a[i].y-b[j].y)/(1.0*(a[i].x-b[j].x));
                if(a[i].x==b[j].x)xielv=1e-15;
                double jieju=a[i].y-1.0*a[i].x*xielv;
                double xl=-1.0/xielv;
                double jj=c[q].y-1.0*c[q].x*xl;
                double xx=(jj-jieju)/(xielv-xl);
                double yy=xx*xielv+jieju;
                if(xx+1e-5>min(a[i].x,b[j].x)&&xx-1e-5<max(a[i].x,b[j].x)&&sqrt((xx-c[q].x)*(xx-c[q].x)+(yy-c[q].y)*(yy-c[q].y))-1e-5<c[q].r)flag=0;
            }
            if(flag)
            {
                t[i].push_back((node){j+n,1}),t[j+n].push_back((node){i,0});
                p[i].push_back(t[j+n].size()-1),p[j+n].push_back(t[i].size()-1);
            }
        }
        t[i].push_back((node){0,0});
        p[0].push_back(t[i].size()-1);
    }
    for(int i=1;i<=m;i++)
    {
        t[i+n].push_back((node){1+n+m,1}),t[1+n+m].push_back((node){i,0});
        p[n+m+1].push_back(t[i+n].size()-1),p[i+n].push_back(t[n+m+1].size()-1);
    }
    for(int i=1;i<=n;i++)p[i].push_back(0);
    int l=0,r=1e9;
    while(l<r)
    {
        int mid=(l+r)>>1;
        t[0].clear();
        for(int i=1;i<=n;i++)
        {
            t[0].push_back((node){i,mid/a[i].t+1});
            p[i][p[i].size()-1]=t[0].size()-1;
        }
        for(int i=1;i<=n+m;i++)
        {
            int len=t[i].size();
            for(int j=0;j<len;j++)
            {
                if(i<t[i][j].to)t[i][j].data=1;
                else t[i][j].data=0;
            }
        }
        int ans=0;
        while(bfs())
        {
            memset(vis,0,sizeof(vis));
            int sum=dfs(0,1e9);
            while(sum)
            {
                ans+=sum;
                memset(vis,0,sizeof(vis));
                sum=dfs(0,1e9);
            }
        }
        if(ans==m)r=mid;
        else l=mid+1;
    }
    int mid=l;
    t[0].clear();
    for(int i=1;i<=n;i++)
    {
        t[0].push_back((node){i,mid/a[i].t+1});
        p[i][p[i].size()-1]=t[0].size()-1;
    }
    for(int i=1;i<=n+m;i++)
    {
        int len=t[i].size();
        for(int j=0;j<len;j++)
        {
            if(i<t[i][j].to)t[i][j].data=1;
            else t[i][j].data=0;
        }
    }
    int ans=0;
    while(bfs())
    {
        memset(vis,0,sizeof(vis));
        int sum=dfs(0,1e9);
        while(sum)
        {
            ans+=sum;
            memset(vis,0,sizeof(vis));
            sum=dfs(0,1e9);

        }
    }
    if(ans!=m)printf("-1");
    else printf("%d",l);
    return 0;
}