1 条题解

  • 0
    @ 2021-8-8 10:44:37

    C++ :

    
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    #include<cmath>
    using namespace std;
    const int maxn=50+10;
    struct Node
    {
        int x,y;
        Node() {}
        Node(int a,int b):x(a),y(b) {}
    } def[maxn],ta[maxn];
    int vis[maxn*maxn],pre[maxn*maxn];
    double times[maxn][maxn];
    double t1,t2,V;
    vector<int >G[maxn];
    int n,m;
    bool DFS(int u)
    {
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            if(vis[v])
                continue;
            vis[v]=1;
            if(pre[v]==0||DFS(pre[v]))
            {
                pre[v]=u;
                return true;
            }
        }
        return false;
    }
    bool judge(double mid)
    {
        for(int i=1; i<=m; i++)
            G[i].clear();
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
            {
                double now=0;
                for(int k=0; k<=m; k++)
                {
                    now=k*(t1+t2);
                    if(mid-(now+t1+times[i][j])>1e-7)
                    {
                        G[i].push_back(j*(m+1)+k-m-1);
                    }
                    else
                        break;
                }
            }
        memset(pre,0,sizeof(pre));
        for(int i=1; i<=m; i++)
        {
            memset(vis,0,sizeof(vis));
            if(!DFS(i))
                return false;
        }
        return true;
    }
    int main()
    {
        cin>>n>>m>>t1>>t2>>V;
        t1/=60.0;
        for(int i=1; i<=m; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            ta[i]=Node(x,y);
        }
        for(int i=1; i<=n; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            def[i]=Node(x,y);
        }
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
                times[i][j]=sqrt((ta[i].x-def[j].x)*(ta[i].x-def[j].x)+(ta[i].y-def[j].y)*(ta[i].y-def[j].y))/V;
    
        double l=0,r=1000000,ans=r;
        while(r-l>1e-9)
        {
            double mid=(l+r)/2.0;
            if(judge(mid))
                ans=min(ans,mid),r=mid;
            else
                l=mid;
        }
        printf("%.6lf\n",ans);
    }
    
    
    • 1

    信息

    ID
    284
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    5
    已通过
    4
    上传者