contest hunter 6803 导弹防御塔

没什么好写的。写写这题吧

拆点，把一个防御塔拆成m个，表示第i次攻击。瞎yy就好啊

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct node

{

    int x,y,next;

}a[];int len,last[];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

int tim,v[],match[];

bool findmuniu(int x)

{

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(v[y]!=tim)

        {

            v[y]=tim;

            if(match[y]==||findmuniu(match[y])==true)

            {

                match[y]=x;

                return true;

            }

        }

    }

    return false;

}

int n,m;double T1,T2,V;

struct point{double x,y;}p[],q[];

double getdis(int i,int j)

{

    return sqrt((p[i].x-q[j].x)*(p[i].x-q[j].x)+(p[i].y-q[j].y)*(p[i].y-q[j].y))/V;

}

bool check(double mid)

{

    len=;memset(last,,sizeof(last));

    for(int i=;i<=n;i++)

    {

        bool bk=true;

        for(int u=;u<=m;u++)

        {

            bk=false;

            for(int j=;j<=m;j++)

                if(u*T1+(u-)*T2+getdis(i,j)<=mid)

                    ins((u-)*n+i,j), bk=true;

            if(bk==false)break;

        }

    }

    int ans=;

    tim=;memset(v,,sizeof(v));

    memset(match,,sizeof(match));

    for(int i=;i<=n;i++)

    {

        int u=;

        for(int u=;u<=m;u++)

        {

            tim++;

            if(findmuniu((u-)*n+i))tim++,ans++;

            else break;

        }

    }

    return ans==m;

}

int main()

{

    scanf("%d%d%lf%lf%lf",&n,&m,&T1,&T2,&V);T1/=;

    for(int i=;i<=m;i++)scanf("%lf%lf",&q[i].x,&q[i].y);

    for(int i=;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);

    double l=,r=;

    while(r-l>1e-)

    {

        double mid=(l+r)/;

        if(check(mid))r=mid;

        else l=mid;

    }

    printf("%.6lf\n",l);

    return ;

}