AcWing374 导弹防御塔

2021-02-03 00:14

阅读：527

标签：stdin 二分答案代码 for double inf return pen c++

二分图

此题看书的时候觉得特别难，实际的代码却非常简单

现在分析是什么让代码如此简单的：

首先预处理出第i个防御塔发射第j个导弹的时间（计算发射时间，不计冷却时间）
二分答案，判断时间mid内能否解决问题
利用vector建边，不用管标号的冲突，在二分图中十分方便（一般网络流可能就没办法了）

时间复杂度：\(O(n^4*log(T))\) 实际更快

#include
using namespace std;

#define go(i,a,b) for(int i=a;i=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))

const int inf=0x3f3f3f3f,N=60,M=2510;
const double eps=1e-8;
typedef long long ll;

int n,m,v,match[M],tot;
bool vis[M];
double t1,t2;
vectore[N];
struct node{
    double x,y;
}a[N],b[N];
struct new_node{
    int id;double t;
}c[M];

bool dfs(int u){
    for(int i=0;ieps){
        double mid=(l+r)*0.5;
        if(pd(mid)) r=mid;
        else l=mid;
    }
    printf("%.6lf",r);
    return 0;
}

AcWing374 导弹防御塔

标签：stdin 二分答案代码 for double inf return pen c++

原文地址：https://www.cnblogs.com/White-star/p/11526325.html

上一篇：c# 对象赋值踩坑

下一篇：Windows删除文件夹下的指定格式文件（递归删除）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing374 导弹防御塔
文章链接：http://soscw.com/essay/50172.html

亲，登录后才可以留言！

AcWing374 导弹防御塔

二分图

时间复杂度：\(O(n^4*log(T))\) 实际更快

评论

热门文章

推荐文章

最新文章

置顶文章