锐客网

  1. 首页 > it技术 > >

online|hdu3622Bomb Game

图论HDUonline2-SATjudge

链接：http://acm.hdu.edu.cn/showproblem.php?pid=3622
题意：给定n对点，每对点需要选择其中之一放一个炸弹，炸弹的半径随意，但是两个炸弹的爆炸覆盖面积不允许重叠。求使得所有炸弹半径中最小值最大的那个最大值。
分析：最小值最大很经典就是二分答案，然后怎么判断呢？我们根据两两之间的互斥关系建立一些表达式然后就是一个2-sat问题啦。
代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef double db; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; const db eps=1e-4; const int N=4e2+10; const int M=1e5+10; const ll MOD=100007; const int mod=1000000007; const int MAX=1000000010; const double pi=acos(-1.0); struct twosat { int n,k,d[N]; bool mark[N]; int tot,u[N],v[M],pre[M]; void init(int a) { n=a<<1; tot=0; for (int i=0; ieps) if (pd(mid)) l=mid,mid=(l+r)/2.0; else r=mid,mid=(l+r)/2.0; printf("%.2f\n", l); } return 0; }



    推荐阅读


    上一篇：喝真正的红葡萄酒

    下一篇：online|hdu1816Get Luffy Out *