首页 > 代码库 > HDU3622(二分+2-SAT)
HDU3622(二分+2-SAT)
题意不说了,直接讲思路。
首先对半径进行二分,然后再判断炸弹之间的距离是否小于2*半径,如果是,那么就连接i->j^1和j->i^1,然后用强连通判断可行性。
#include <stdio.h> #include <string.h> #include <string> #include <iostream> #include <algorithm> #include <vector> #include <math.h> #include <map> #include <queue> #include <stack> #include <set> #define M 205 #define LL long long #define Ld __int64 #define eps 0.00001 #define INF 999999999 #define MOD 112233 #define MAX 26 using namespace std; struct Node { double x,y; }; struct Node node[M]; vector<int> G[M]; //dfn数组表示dfs时到达i点的时间,indx表示时间 int dfn[M],low[M],sccno[M],scc_cnt; int indx; int num[M]; stack<int> s; void Tarjan(int u) { indx++; dfn[u]=low[u]=indx; //为结点u设定次序编号和low初值 s.push(u); //将结点u压入栈中 for(int i=0;i<G[u].size();i++) //枚举每条边 { int v=G[u][i]; if(!dfn[v]) //若结点v未被访问过 { Tarjan(v); //继续往下找 low[u]=min(low[u],low[v]); } else if(!sccno[v]) //若结点v在栈中 { low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]) //如果结点u是强连通分量的根 { scc_cnt++; for(;;) { int x=s.top(); //讲v退栈,为该强连通分量中一个顶点 s.pop(); sccno[x]=scc_cnt; num[scc_cnt]++; //记录每个强连通分量的结点数 if(x==u) break; } } } void find_scc(int n) { indx=scc_cnt=0; memset(num,0,sizeof(num)); memset(sccno,0,sizeof(sccno)); memset(dfn,0,sizeof(dfn)); for(int i=0;i<n*2;i++) if(!dfn[i]) Tarjan(i); } double distant(Node a,Node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double maxn(double a,double b) { if(a<b) return b; return a; } int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i<n*2;i+=2) { scanf("%lf%lf%lf%lf",&node[i].x,&node[i].y,&node[i^1].x,&node[i^1].y); } double l=0.0,r=40000.0; double ans=-1; while(r-l>eps) { double mid=(l+r)/2; for(int i=0;i<n*2;i++) G[i].clear(); for(int i=0;i<n*2;i+=2) { for(int j=i+2;j<n*2;j++) { if(distant(node[i],node[j])<2*mid) { G[i].push_back(j^1); G[j].push_back(i^1); } } } for(int i=1;i<n*2;i+=2) { for(int j=i+1;j<n*2;j++) { if(distant(node[i],node[j])<2*mid) { G[i].push_back(j^1); G[j].push_back(i^1); } } } find_scc(n); int flag=0; for(int i=0;i<n*2;i+=2) { if(sccno[i]==sccno[i+1]) { flag=1; break; } } if(flag) { r=mid; } else { l=mid; ans=mid; } } printf("%.2lf\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。