`
暴风雪
  • 浏览: 390596 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[二分+匈牙利]zoj 3460:Missile

阅读更多

大致题意:
    用n个导弹发射塔攻击m个目标。每个发射架在某个时刻只能为一颗导弹服务,发射一颗导弹需要准备t1的时间,一颗导弹从发射到击中目标的时间与目标到发射架的距离有关。每颗导弹发射完成之后发射架需要t2的时间进入下个发射流程。现在问最少需要多少时间可以击毁所有m个目标。

 

大致思路:
    二分枚举这个最大时间的最小值,每次按照这个枚举的时间构出二分图,求最大匹配来判定枚举值是否符合要求。

 

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
const int inf=1<<30;
const double eps=1e-8;
int N,M;
double tt1,tt2,v;
int mis[100][2],tar[100][2];
double dis[3000][60];

double getdis(int a,int b)
{
    double tmp=(mis[a][0]-tar[b][0])*(mis[a][0]-tar[b][0])+(mis[a][1]-tar[b][1])*(mis[a][1]-tar[b][1]);
    double res=sqrt(tmp);
    return res;
}
void getinit()
{
    int i,j,k;
    for(i=1;i<=N;i++)  // 枚举第i个发射塔
    {
        for(j=1;j<=M;j++)  //第i个发射塔的第j次发射
        {
            for(k=1;k<=M;k++)  //第j次发射,攻击第k个目标
            {
                dis[(i-1)*M+j][k]=(j-1)*tt2+getdis(i,k)/v+j*tt1;
            }
        }
    }
}

int map[3000][60];
bool vis[3000];
int linkk[3000];

int dfs(int s){
    for(int i=1;i<=M;i++){
        if(!vis[i]&&map[s][i]){
            vis[i]=1;
            if(linkk[i]==-1||dfs(linkk[i])){
                linkk[i]=s;
                return 1;
            }
        }
    }
    return 0;
}

bool check(double mid)
{
//    cout<<"check"<<mid<<endl;
    int i,j,res=0;
    memset(map,0,sizeof(map));
    for(i=1;i<=N*M;i++)
    {
        for(j=1;j<=M;j++)
        {
            if(dis[i][j]<=mid)
            {
                map[i][j]=1;
            }
        }
    }
    memset(linkk,-1,sizeof(linkk));
    for(i=1;i<=N*M;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))res++;
    }
    if(res==M)return 1;
    return 0;
}

int main()
{
    int i;
    while(scanf("%d%d%lf%lf%lf",&N,&M,&tt1,&tt2,&v)!=EOF)
    {
        tt1/=60.0;
        for(i=1;i<=M;i++)
        {
            scanf("%d%d",&tar[i][0],&tar[i][1]);
        }
        for(i=1;i<=N;i++)
        {
            scanf("%d%d",&mis[i][0],&mis[i][1]);
        }
        getinit();
        double left=0,right=200000000,mid;
        while(right-left>=eps)
        {
            mid=(left+right)/2.0;
            if(check(mid))right=mid;
            else left= mid;
        }
        printf("%.6f\n",left);
    }
    return 0;
}
 
0
1
分享到:
评论

相关推荐

    ZOJ:浙江大学程序在线评测系统.docx

    ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...

    浙江大学ZOJ题目分类

    浙江大学ZOJ题目分类旨在为编程学习者提供一个系统化的训练平台,帮助他们在算法和编程技能上实现质的飞跃。ZOJ平台提供的分类题目包括但不限于基础算法、数据结构、动态规划以及模拟问题等,这些分类覆盖了计算机...

    zoj 源码700题

    3. **算法与数据结构**:700题涵盖的范围广泛,涉及基本的排序算法(如冒泡、快速、归并排序),查找算法(如二分查找),以及高级算法如动态规划(如斐波那契数列、背包问题)、图论(如最短路径、最小生成树)、...

    zoj 1002_zoj1002_

    【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...

    ACM训练必备POJ ZOJ题目分类及解题思路

    学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路

    zoj 分类加题解(浙大ACM)

    《ZOJ ACM分类加题解》是针对浙江大学ACM竞赛训练平台的一份宝贵资源,它包含了大量的编程竞赛题目和相应的解答。这份资料旨在帮助参赛者提升算法能力,提高解决实际问题的技巧,无论是在无网络环境下还是有网络时,...

    pku hdu zoj题目分类

    "POJ 计算几何入门题目.doc"可能介绍了计算几何的基础知识,并提供了一些实践题目,这个领域涉及点、线、面的相互关系,以及在二维和三维空间中的几何操作。 5. **ZOJ题目分类**: "zoj题目分类.doc"对应浙江大学...

    zoj1027解题指南

    【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...

    zoj 题库 详细解答 解题代码

    zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...

    ZOJ题目答案源码

    首先,我们可以从这些源代码中学习到基础的算法思想,如排序算法(快速排序、归并排序、冒泡排序、插入排序等)、搜索算法(二分查找、深度优先搜索、广度优先搜索等)。这些算法是解决问题的基本工具,理解和掌握...

    zoj 700源代码

    ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...

    ZOJ题解集合-截至2835

    1. **基础算法**:包括排序(如快速排序、归并排序)、搜索(如二分查找)、动态规划、贪心算法、回溯算法等。 2. **高级数据结构**:如链表、树(二叉树、平衡树如AVL和红黑树)、图(深度优先搜索、广度优先搜索...

    ZOJ1004回溯+深搜

    深度搜索 回溯 int main { string s1 s2; while cin &gt;&gt; s1 &gt;&gt; s2 { count 0; cout &lt;&lt; &quot;[&quot; &lt;&lt; endl; if s1 length s2 length BackTrake s1 s2 ;... [更多]

    Problem Arrangement zoj 3777

    Problem Arrangement zoj 3777

    zoj.rar_zoj_zoj4041

    《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...

    zoj.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar

    标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...

    ZOJ月赛 题解 (ZOJ Monthly, August 2014)

    **ZOJ月赛题解 (ZOJ Monthly, August 2014)** ZOJ(Zhejiang Online Judge)是中国著名的在线编程竞赛平台之一,它为程序员和学生提供了丰富的算法练习和比赛机会。2014年8月的ZOJ月赛是一场面向广大编程爱好者的...

    zoj代码集合

    1. **基础算法**:作为入门部分,这个集合可能包括基础数据结构和算法,如排序(快速排序、归并排序、堆排序)、查找(二分查找、哈希表查找)以及图论的基本概念(Dijkstra、Floyd等)。这些是所有ACM竞赛者必须...

    ZOJ1003 Crashing Balloon

    【ZOJ1003 Crashing Balloon】这个问题是一个经典的计算机科学竞赛编程题目,主要涉及动态规划(Dynamic Programming, DP)和贪心算法(Greedy Algorithm)的知识点。在这个问题中,参赛者需要编写程序来模拟气球...

Global site tag (gtag.js) - Google Analytics