HDOJ 3622 - Bomb Game 2-sat+二分....细心...

网友投稿 299 2022-11-06


HDOJ 3622 - Bomb Game 2-sat+二分....细心...

题意:

有N个炸弹..每个炸弹有两个位置可以选择..把炸弹放到其中一个地方去...炸弹的爆炸范围是其为圆心的圆...两个炸弹不能有攻击范围上的重合..问要满足条件..炸弹爆炸范围的半径最长能是多少...

题解:

每个炸弹看成一类..其在两个中比选一个..符合2-sat的构图条件....那么就二分枚举炸弹的爆炸范围..枚举相互是否干扰来做边构造2-sat模型...tarjan来判断是否合法..

题目不难..但是我2B了...在初始化vector时..for (i=0;i<(n<<1);i++)  T[i].clear() 写成了for (i=0;i<(1<

Program-----链表存图..整个程序int型计算..结果再开方除2输出

#include#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 205#define MAXM 100005using namespace std;struct node{ int x0,y0,x1,y1;}b[MAXN];struct LINE{ int x,y,next;}line[MAXM];int Lnum,_next[MAXN],dfn[MAXN],low[MAXN],tp[MAXN],tpnum,DfsIndex,arc[MAXN][MAXN];bool instack[MAXN];stack mystack;int dis(int x0,int y0,int x1,int y1){ return (x0-x1)*(x0-x1)+(y0-y1)*(y0-y1);}void addline(int x,int y){ line[++Lnum].next=_next[x],_next[x]=Lnum; line[Lnum].x=x,line[Lnum].y=y;}void tarjan(int x) { int y,k; dfn[x]=low[x]=++DfsIndex; instack[x]=true; mystack.push(x); for (k=_next[x];k;k=line[k].next) { y=line[k].y; if (!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); }else if (instack[y]) low[x]=min(low[x],dfn[y]); } if (dfn[x]==low[x]) { tpnum++; do { x=mystack.top(); mystack.pop(); instack[x]=false; tp[x]=tpnum; }while (dfn[x]!=low[x]); } return; } bool _2sat(int n,int d){ int i,j; Lnum=0; memset(_next,0,sizeof(_next)); for (i=0;i1) { mid=(r+l)/2; if (_2sat(n,mid)) l=mid; else r=mid; } printf("%.2lf\n",sqrt(l)*0.5); } return 0;}

Program-----vector存图..其他同上

#include#include#include#include#include#include#include#include#include#define ll long long#define oo 1000000007#define pi acos(-1.0)#define MAXN 205using namespace std;struct node{ int x0,y0,x1,y1;}b[MAXN];vector T[MAXN];int dfn[MAXN],low[MAXN],tp[MAXN],tpnum,DfsIndex,arc[MAXN][MAXN];bool instack[MAXN];stack mystack;int dis(int x0,int y0,int x1,int y1){ return (x0-x1)*(x0-x1)+(y0-y1)*(y0-y1);}void tarjan(int x) { int i,y,m=T[x].size(); dfn[x]=low[x]=++DfsIndex; instack[x]=true; mystack.push(x); for (i=0;i1) { mid=(r+l)>>1; if (_2sat(n,mid)) l=mid; else r=mid; } printf("%.2f\n",sqrt(l)*0.5); } return 0;}

Program-----vector存图..直接浮点进行运算...

#include#include#include#include#include#include#include#include#include#define ll long long#define eps 1e-5#define oo 1000000007#define pi acos(-1.0)#define MAXN 205using namespace std;struct node{ int x0,y0,x1,y1;}b[MAXN];vector T[MAXN];int dfn[MAXN],low[MAXN],tp[MAXN],tpnum,DfsIndex;double arc[MAXN][MAXN];bool instack[MAXN];stack mystack;double dis(int x0,int y0,int x1,int y1){ return sqrt((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1));}void tarjan(int x) { int i,y,m=T[x].size(); dfn[x]=low[x]=++DfsIndex; instack[x]=true; mystack.push(x); for (i=0;ieps) { mid=(r+l)/2; if (_2sat(n,mid)) l=mid; else r=mid; } printf("%.2lf\n",l*0.5); } return 0;}


版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：代码
上一篇:京东快递查询单号查询API（京东快递查询单号查询 快递单号）
下一篇:深圳交通违章查询API（深圳交通违章查询电话）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~