【练习一】
http://acm.hdu.edu.cn/showproblem.php?pid=3622这题是2010天津网络赛试题。
二分答案，将圆看做一个点，当两个圆a,b的距离小于给定距离d时，说明a,b互斥，连边<a , ~b> ，<~b , a> 。
二分+ 2_SAT 。 这确实是个好思路。
/**//**//**//*
2010 Asia Tianjin Regional online Contest
Problem B: Bomb Game
Methord : binary search + 2-SAT
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std ;
const int MAXN = 205 ;
const int MAXE = MAXN*MAXN ;
const double EPS = 1e-3 ;
struct Edge
{
int y , next;
};
struct Point{
double x , y ;
};
Edge e[MAXE] ;
Point P[MAXN] ;
int es , hd[MAXN] , n ;
double dist[MAXN][MAXN] ;
inline int sgn(double x){
return (x>EPS)-(x<-EPS);
}
inline void ins(int x ,int y){
e[es].y = y , e[es].next = hd[x] , hd[x] = es ++ ;
}
inline double cal(Point a, Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)) ;
}
int low[MAXN] ,dfn[MAXN],stk[MAXN] , instk[MAXN] , bel[MAXN] , bcnt , idx , top;
void Tarjan(int x ){
int i , y;
low[x] = dfn[x] = ++idx ;
stk[top++] = x ; instk[x] = 1 ;
for(i = hd[x] ; i!=-1 ; i=e[i].next){
y = e[i].y ;
if(dfn[y]==-1){
Tarjan(y) ;
low[x] = min(low[x] , low[y]) ;
}else if(instk[y]){
low[x] = min(low[x] , dfn[y]) ;
}
}
if(low[x] == dfn[x]){
++ bcnt ;
do{
y = stk[--top] ;
instk[y] = 0 ;
bel[y] = bcnt ;
}while(y!=x);
}
}
int check(double d){
int i , j , k ;
es = 0 ; memset(hd , -1 ,sizeof(hd));
for(i = 1 ; i<= n; ++i){
for(j = i+1 ; j<=n ; ++j){
if(dist[2*i-1][2*j-1]< d )
ins(2*j-1 , 2*i) , ins(2*i-1 , 2*j);
if(dist[2*j-1][2*i]< d)
ins(2*j-1 , 2*i-1) , ins(2*i ,2*j);
if(dist[2*j][2*i-1]< d)
ins(2*j , 2*i) , ins(2*i-1,2*j-1);
if(dist[2*j][2*i]< d)
ins(2*j , 2*i-1) , ins(2*i,2*j-1);
}
}
idx = bcnt = top = 0 ;
memset(dfn , -1 ,sizeof(dfn));
memset(instk , 0,sizeof(instk));
for(i = 1 ; i<=2*n ;++i)
if(dfn[i] == -1)
Tarjan(i);
for(i = 1 ; i<=n ; ++i)
if(bel[2*i-1] == bel[2*i]) return 0 ;
return 1;
}
int main(){
int i , j ;
double l , r ,mid ;
while(scanf("%d" , &n)!=EOF){
for(i = 1 ; i <=2*n ; ++i)
scanf("%lf%lf",&P[i].x ,&P[i].y);
for(i = 1 ; i <=2*n ; ++i)
for(j = 1 ; j<=2*n ; ++j)
dist[i][j] = cal(P[i] ,P[j]);
l = 0 , r = 1e6 ;
while(sgn(l-r)){
mid = (l + r) / 2.0 ;
if(check(mid))
l = mid ;
else
r = mid ;
}
printf("%0.2lf\n" , l/2.0);
}
return 0 ;
}
【练习二】
http://poj.org/problem?id=3207只能遗憾的讲，这题考晦涩。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<memory>
#define MAXN 1005
using namespace std ;
int l[501] , r[501] , n , m;
bool gh[1001][1001];
bool IsCross(int x ,int y){
return (l[y]<=l[x] && l[x]<=r[y]) != (l[y]<=r[x] && r[x]<=r[y]) ;
}
int bcnt , top , idx , stk[MAXN] ,instk[MAXN] , dfn[MAXN] ,low[MAXN] , bel[MAXN];
void Tarjan(int x){
int y ;
dfn[x] = low[x] = ++ idx ;
instk[x] = 1 ; stk[top++] = x ;
for(y = 1 ; y<=2*m ; ++y)
if(gh[x][y]){
if(dfn[y] == -1){
Tarjan(y);
low[x] = min(low[x] , low[y]) ;
}else if(instk[y]){
low[x] = min(low[x] , dfn[y]) ;
}
}
if( dfn[x] == low[x]){
++ bcnt ;
do{
y = stk[--top] ;
instk[y] = 0 ;
bel[y] = bcnt ;
}while(y!=x);
}
}
int main(){
int i , j , k , ans;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= m ; ++i){
scanf("%d%d" ,&l[i] , &r[i]);
if(l[i] > r[i]) swap(l[i] , r[i]);
}
memset(gh , 0 , sizeof(gh));
for(i = 1 ; i <= m ; ++ i){
for( j = i + 1 ; j<= m ; ++j)
if(IsCross(i , j)){
gh[2*i-1][2*j] = gh[2*j-1][2*i] = 1 ;
gh[2*i][2*j-1] = gh[2*j][2*i-1] = 1 ;
}
}
bcnt = top = idx = 0 ;
memset(dfn , -1 ,sizeof(dfn));
memset(instk ,0 ,sizeof(instk));
for(i = 1 ; i <=2*m ; ++i)
if(dfn[i] == -1)
Tarjan(i);
ans = 1 ;
for(i = 1 ; i<=m ; ++i)
if(bel[2*i-1] == bel[2*i]){
ans = 0 ; break ;
}
if(ans)
printf("panda is telling the truth\n");
else
printf("the evil panda is lying again\n");
return 0 ;
}
【练习三】
http://poj.org/problem?id=3678题目中的0,1让建模显得不是那么难了。
#include<iostream>
#include<cstring>
#define MAXN 2005
using namespace std ;
struct Edge{
int y , next ;
};
Edge e[MAXN*MAXN] ;
int es , hd[MAXN];
int Vcnt , Ecnt ;
inline void ins(int x ,int y){
e[es].y = y , e[es].next = hd[x] , hd[x] = es ++ ;
}
bool cal(bool x , bool y , char cmd[]){
if(!strcmp(cmd ,"AND")){
return x & y ;
}else if(!strcmp(cmd ,"OR")){
return x|y ;
}else if(!strcmp(cmd,"XOR")){
return x^y ;
}
}
int bcnt , top , idx ;
int stk[MAXN] ,instk[MAXN] ,dfn[MAXN] , low[MAXN] ,bel[MAXN];
void Tarjan(int x){
int i ,y ;
dfn[x] = low[x] = ++ idx ;
instk[x] = 1 , stk[top++] = x ;
for(i = hd[x] ; i!=-1 ;i=e[i].next){
y = e[i].y ;
if(dfn[y] == -1){
Tarjan(y) ;
low[x] = min(low[x] ,low[y]) ;
}else if(instk[y]){
low[x] = min(low[x] ,dfn[y]);
}
}
if( low[x] == dfn[x]){
++ bcnt ;
do{
y = stk[--top] ; instk[y] = 0 ; bel[y] = bcnt ;
}while(y!=x);
}
}
int main(){
int i , x , y , c;
char cmd[10] ;
scanf("%d%d" , &Vcnt ,&Ecnt);
es = 0 ; memset(hd , -1 ,sizeof(hd));
while(Ecnt--){
scanf("%d%d%d%s",&x,&y,&c,cmd); ++ x ; ++ y ;
if(cal(0,0,cmd) != c ){
ins(2*x-1,2*y) , ins(2*y-1,2*x) ;
}
if(cal(0,1,cmd) != c){
ins(2*x-1,2*y-1) ,ins(2*y,2*x) ;
}
if(cal(1,0,cmd) != c){
ins(2*x ,2*y) , ins(2*y-1,2*x-1) ;
}
if(cal(1,1,cmd) != c){
ins(2*x,2*y-1) , ins(2*y,2*x-1);
}
}
bcnt = idx = top = 0 ;
memset(dfn , -1 , sizeof(dfn)) ;
memset(instk , 0 , sizeof(instk));
for(i = 1 ; i<=Vcnt*2 ; ++i)
if(dfn[i] == -1)
Tarjan(i);
for(i = c = 1 ; i<=Vcnt ;++i)
if(bel[2*i-1] == bel[2*i] ){
c = 0 ; break ;
}
if(c)
puts("YES");
else
puts("NO");
return 0 ;
}
【练习四】
http://poj.org/problem?id=2723想来想去，还是这个题目比较经典。
老规矩，二分 + 2_SAT判断。
有两种思维方式：
<1>. 2*N个钥匙用或不用 ;
<2>. 每扇门用锁a或者锁b ;
但是，仔细想来<1>的建图复杂度更低，而我却遗憾的用了<2>。
介绍两个版本：
版本一：
http://blog.csdn.net/xiaotiandm/archive/2010/10/11/5933651.aspx版本二：
#include<iostream>
#define MAXN ((1<<12)+3)
using namespace std;
int key , door , Pair[MAXN] , lock[MAXN] , N;
bool gh[MAXN][MAXN] , instk[MAXN];
int bcnt ,idx ,top , dfn[MAXN] , low[MAXN],stk[MAXN] , bel[MAXN];
void Tarjan(int x){
int i , y ;
low[x] = dfn[x] = ++ idx ;
instk[x] = 1 , stk[top ++ ] = x ;
for(y = 0 ; y < N ; ++ y)
if(gh[x][y]){
if(dfn[y] == -1){
Tarjan(y) ;
low[x] = min(low[x] , low[y]) ;
}else if(instk[y]){
low[x] = min(low[x] , dfn[y]) ;
}
}
if(low[x] == dfn[x]){
++ bcnt ;
do{
y = stk[--top] ; instk[y] = 0 ; bel[y] = bcnt;
}while(y!=x);
}
}
bool check(int MAX_DOOR){
int i , j , k ;
N = 2*MAX_DOOR ;
for(i = 0 ; i < N ; ++i)
for(j = 0 ; j < N ; ++j)
gh[i][j] = 0 ;
for(i = 0 ; i < MAX_DOOR ; ++ i)
for(j = i + 1; j < MAX_DOOR ; ++j){
if(Pair[lock[2*i]] == lock[2*j]) gh[2*i][2*j+1] = gh[2*j][2*i+1] = 1;
if(Pair[lock[2*i]] == lock[2*j+1]) gh[2*i][2*j] = gh[2*j+1][2*i+1] = 1;
if(Pair[lock[2*i+1]] == lock[2*j]) gh[2*i+1][2*j+1]= gh[2*j][2*i] = 1;
if(Pair[lock[2*i+1]] == lock[2*j+1]) gh[2*i+1][2*j] = gh[2*j+1][2*i] = 1;
}
bcnt = top = idx = 0 ;
for(i = 0 ; i < N ; ++ i) instk[i] = 0 , dfn[i] = -1 ;
for(i = 0 ; i < N ; ++ i)
if(dfn[i] == -1) Tarjan(i);
for(i = 0 ; i < MAX_DOOR ; ++ i)
if(bel[2*i] == bel[2*i+1]) return false;
return true;
}
int main(){
int i ,x , y , l , r , mid , ans;
while(scanf("%d%d", &key,&door)!=EOF && (key+door)){
for(i = 0 ; i<key ; ++i){
scanf("%d%d",&x,&y);
Pair[x] = y , Pair[y] = x ;
}
for(i = 0 ; i<2*door ;++i) scanf("%d" , &lock[i]);
ans = 1 , l = 1 , r = door ;
while(l <= r){
mid = (l + r) / 2 ;
if(check(mid)){
ans = mid ; l = mid + 1 ;
}else{
r = mid - 1;
}
}
printf("%d\n" , ans);
}
return 0 ;
}