当前位置：编程学习 > C/C++ >>

ZOJ 3717 HDU 3622 二分+2-SAT

题意：给你N组气球，每组有2个气球，每组要取一个气球，问最后使得N个气球都不相交，则气球半径R最大是多少。

思路：直接二分半径，然后2-sat判可行性。SCC之后如果有两个同组的点在同一个强联通分量里，那么则不可行。

这道题注意最后的二分结束之后还要取三位小数，看取了之后是否还是符合情况的，最后的那个 操作是看别人的。。我WA到死了。。

我感觉这题这里太坑了。。。

 #include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 2505  
#define inf 1<<28  
#define LL(x) ( x << 1 )  
#define RR(x) ( x << 1 | 1 )  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define PII pair<int,int>  
using namespace std; 
 
int t ; 
#define N 2005  
double x[N << 1] , y[N << 1] ,z[N << 1] ; 
 
struct kdq{ 
    int e , next ; 
}ed[N * 100] ; 
int head[N] , num ; 
int dfn[N << 1] , low[N << 1] ,st[N << 1] , top , dp ,inst[N << 1] , ca ,belong[N << 1] ; 
void add(int s ,int e){ 
    ed[num].e = e ; 
    ed[num].next = head[s] ; 
    head[s] = num ++ ; 
} 
void init(){ 
    mem(head , -1) ; 
    num = 0 ; 
    mem(dfn ,0) ; 
    mem(low, 0) ; 
    mem(st ,0) ; 
    mem(inst ,0) ; 
    mem(belong ,0) ; 
    top = dp = ca = 0 ; 
} 
inline double getdis(int i ,int j){ 
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j])) ; 
} 
 
void tarjan(int now){ 
    low[now] = dfn[now] = ++ dp ; 
    st[top ++] = now ; 
    inst[now] = 1 ; 
    for (int i = head[now] ; ~i ; i = ed[i].next ){ 
        int e = ed[i].e ; 
        if(!dfn[e]){ 
            tarjan(e) ; 
            low[now] = min(low[now] , low[e])  ; 
        } 
        else if(inst[e]){ 
            low[now] = min(low[now] , dfn[e]) ; 
        } 
    } 
    if(low[now] == dfn[now]){ 
        ca ++ ; 
        int xx ; 
        do{ 
            xx = st[-- top] ; 
            belong[xx] = ca ; 
            inst[xx] = 0 ; 
        }while(xx != now) ; 
    } 
} 
void build(double mid){ 
    init() ; 
    for (int i = 0 ; i < t ; i ++ ){ 
        for (int j = i + 1 ; j  < t ; j ++ ){ 
            if(getdis(LL(i),LL(j)) < mid){ 
                add(LL(i) , LL(j) ^ 1) ; 
                add(LL(j) , LL(i) ^ 1) ; 
            } 
            if(getdis(LL(i) ,RR(j)) < mid){ 
                add(LL(i) , RR(j) ^ 1) ; 
                add(RR(j) , LL(i) ^ 1) ; 
            } 
            if(getdis(RR(i) , LL(j)) < mid){ 
                add(RR(i) , LL(j) ^ 1) ; 
                add(LL(j) , RR(i) ^ 1) ; 
            } 
            if(getdis(RR(i) , RR(j)) < mid){ 
                add(RR(i) , RR(j) ^ 1) ; 
                add(RR(j) , RR(i) ^ 1) ; 
            } 
        } 
    } 
} 
 
int 易做图it(){ 
    for (int i = 0 ; i  < t << 1 ; i ++ ){ 
        top = dp = 0 ; 
        if(!dfn[i])tarjan(i) ; 
    } 
    for (int i = 0 ; i < t ; i ++ ){ 
        if(belong[LL(i)] == belong[RR(i)])return 0 ; 
    } 
    return 1 ; 
} 
int main() { 
 
    while(cin >> t){ 
        for (int i = 0 ; i < t ;i ++ ){ 
            cin >> x[LL(i)] >> y[LL(i)] >> z[LL(i)] ; 
            cin >> x[RR(i)] >> y[RR(i)] >> z[RR(i)] ; 
        } 
//        cout << getdis(0 ,1) << endl;  
        double l = 0 , r = 20000 ; 
        double mid ; 
        while(r - l > 1e-5){ 
            mid = (l + r) / 2 ; 
            build(mid) ; 
            if(易做图it()){ 
                l = mid ; 
            } 
            else r = mid ; 
        } 
        double ans = mid / 2 ;//直接输出 mid / 2 就WA到死。  
        char aa[222] ;//太恶心。  
        sprintf(aa ,"%.3f" , ans) ; 
        sscanf(aa , "%lf" ,&ans) ; 
        build(ans * 2 ) ; 
        if(!易做图it())ans -= 0.001 ; 
        printf("%.3f\n",ans) ; 
    } 
    return 0 ; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;

int t ;
#define N 2005
double x[N << 1] , y[N << 1] ,z[N << 1] ;

struct kdq{
    int e , next ;
}ed[N * 100] ;
int head[N] , num ;
int dfn[N << 1] , low[N << 1] ,st[N << 1] , top , dp ,inst[N << 1] , ca ,belong[N << 1] ;
void add(int s ,int e){
    ed[num].e = e ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;
}
void init(){
    mem(head , -1) ;
    num = 0 ;
    mem(dfn ,0) ;
    mem(low, 0) ;
    mem(st ,0) ;
    mem(inst ,0) ;
    mem(belong ,0) ;
    top = dp = ca = 0 ;
}
inline double getdis(int i ,int j){
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j])) ;
}

void tarjan(int now){
    low[now] = dfn[now] = ++ dp ;
    st[top ++] = now ;
    inst[now] = 1 ;
    for (int i = head[now] ; ~i ; i = ed[i].next ){
        int e = ed[i].e ;
        if(!dfn[e]){
            tarjan(e) ;
            low[now] = min(low[now] , low[e])  ;
        }
        else if(inst[e]){
            low[now] = min(low[now] , dfn[e]) ;
        }
    }
    if(low[now] == dfn[now]){
        ca ++ ;
        int xx ;
        do{
            xx = st[-- top] ;
            belong[xx] = ca ;
            inst[xx] = 0 ;
        }while(xx != now) ;
    }
}
void build(double mid){
    init() ;
    for (int i = 0 ; i < t ; i ++ ){
        for (int j = i + 1 ; j  < t ; j ++ ){
            if(getdis(LL(i),LL(j)) < mid){
                add(LL(i) , LL(j) ^ 1) ;
                add(LL(j) , LL(i) ^ 1) ;
            }
            if(getdis(LL(i) ,RR(j)) < mid){
                add(LL(i) , RR(j) ^ 1) ;
                add(RR(j) , LL(i) ^ 1) ;
            }
            if(getdis(RR(i) , LL(j)) < mid){
                add(RR(i) , LL(j) ^ 1) ;
                add(LL(j) , RR(i) ^ 1) ;
            }
            if(getdis(RR(i) , RR(j)) < mid){
                add(RR(i) , RR(j) ^ 1) ;
                add(RR(j) , RR(i) ^ 1) ;
            }
        }
    }
}

int 易做图it(){
    for (int i = 0 ; i  < t << 1 ; i ++ ){
        top = dp = 0 ;
        if(!dfn[i])tarjan(i) ;
    }
    for (int i = 0 ; i < t ; i ++ ){
        if(belong[LL(i)] == belong[RR(i)])return 0 ;
    }
    return 1 ;
}
int main() {

    while(cin >> t){
        for (int i = 0 ; i < t ;i ++ ){
            cin >> x[LL(i)] >> y[LL(i)] >> z[LL(i)] ;
            cin >> x[RR(i)] >> y[RR(i)] >> z[RR(i)] ;
        }
//        cout << getdis(0 ,1) << endl;
        double l = 0 , r = 20000 ;
        double mid ;
        while(r - l > 1e-5){
            mid = (l + r) / 2 ;
            build(mid) ;
            if(易做图it()){
                l = mid ;
            }
            else r = mid ;
        }
        double ans = mid / 2 ;//直接输出 mid / 2 就WA到死。
        char aa[222] ;//太恶心。
        sprintf(aa ,"%.3f" , ans) ;
        sscanf(aa , "%lf" ,&ans) ;
        build(ans * 2 ) ;
        if(!易做图it())ans -= 0.001 ;
        printf("%.3f\n",ans) ;
    }
    return 0 ;
}

HDU 3622

两道题其实完全是一

补充：软件开发 , C++ ,

上一个：hdu 4452 Running Rabbits (模拟—12年金华赛区现场赛K题)
下一个：hdu 1272 小希的迷宫 （并查集+最小生成树）

更多图片编程知识:
更多C/C++疑问解答：
关于c++的cout输出的问题。
在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
全国计算机二级C语言笔试题
已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
c++数据结构内部排序问题，整数排序
2012九月计算机二级C语言全国题库，，急求急求
如果assert只有一个字符串作为参数，是什么意思呢?
C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
为什么用结构体编写的程序输入是，0输不出来啊~~~
将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
为什么这个程序求不出公式？
这个链表倒置的算法请大家分析下
c语言函数库调用
C语言unsigned int纠错
C语言快排求解啊
asp
php
Delphi
Matlab
JSP
Foxpro
JS
C/C++
C#/ASP.NET
VC++
JAVA
VB
汇编语言
html/css
CGI
XML/UML
wap
网站相关
网页素材
python
微信小程序
thinkphp
如果你遇到编程学习难题：
访问www.zzzyk.com 试试
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络，