[导入]ACM HDU 2528 Mayor's posters（线段树+离散化）

类型：线段树+离散化。

本文作者：kuangbin.

转载请注明writed by kuangbin (博客www.cnblogs.com/kuangbin)

这到题目纠结了我一天，主要是离散化，刚接触线段树不是很熟练。

现在对离散化也有点理解了。

离散化的大概思路 :   比如说给你一组数据 1 4 1000 100000，  如果直接
                         开线段, 显然是浪费, 那么我们只要进行映射 :
                                1    1
                                4    2
                             1000    3
                           100000    4
                         接下来我们只要对 1 2 3 4 建立线段树就行了只需要
                         [1,4]的区间
离散化就相当于是先做映射，然后再建树。

本题大意：给定一些海报，可能相互重叠，告诉你每个海报的宽度（高度都一样的）和先后叠放顺序，问没有被完全盖住的有多少张？

海报最多10000张，但是墙有10000000块瓷砖长，海报不会落在瓷砖中间。

如果直接建树，就算不TLE,也会MLE。即单位区间长度太多。

其实10000张海报，有20000个点，最多有19999个区间。对各个区间编号，就是离散化。然后建数。

其实浮点数也是一样离散化的。

还有好多需要注意的地方。这题的线段树要四倍的，普通的三倍不行了。

细节决定成败：

程序：

/*
HDU 2528 Mayor's posters
本题大意：给定一些海报，可能相互重叠，告诉你每个海报
的宽度（高度都一样的）和先后叠放顺序，问没有被完全盖住的有多少张？
海报最多10000张，但是墙有10000000块瓷砖长，海报不会落在瓷砖中间。
如果直接建树，就算不TLE,也会MLE。即单位区间长度太多。
其实10000张海报，有20000个点，最多有19999个区间。对各个区间编号，就是离散化。然后建数。
其实浮点数也是一样离散化的。

writer:kuangbin
*/
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXN=10010;
struct Cpost
{
    int l,r;
}posters[MAXN];
int x[MAXN*2];
int hash[10000005];
struct Node
{
    int l,r;
    bool bCovered;//标记是否被完全覆盖 
}segTree[MAXN*8];//这里必须开到线段数的四倍，？？ 
void Build(int i,int l,int r)//建立线段树 
{
    segTree[i].l=l;
    segTree[i].r=r;
    segTree[i].bCovered=false;
    if(l==r)return;
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);
    Build(i<<1|1,mid+1,r);
}    
bool Post(int i,int l,int r)//贴上一个好报，同时判断是否被完全覆盖 
{
    if(segTree[i].bCovered)  return false;
    if(segTree[i].l==l&&segTree[i].r==r)
    {
        segTree[i].bCovered=true;
        return true;
    }    
    bool bResult;
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if(r<=mid)  bResult=Post(i<<1,l,r);
    else if(l>mid)
       bResult=Post(i<<1|1,l,r);
    else
    {
        bool b1=Post(i<<1,l,mid);
        bool b2=Post(i<<1|1,mid+1,r);
        bResult=b1||b2;//不能直接或上去，因为如果前面的真，后面的会不做的 
    }
    //这个很重要，要反馈回原结点，如果左右儿子都被完全覆盖了，自然也完全覆盖了 
    if(segTree[i<<1].bCovered && segTree[i<<1|1].bCovered)
        segTree[i].bCovered=true;    
    return bResult;
}    
int main()
{
    int T;
    int i,j,k;
    int n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int nCount=0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&posters[i].l,&posters[i].r);
            x[nCount++]=posters[i].l;
            x[nCount++]=posters[i].r;
        }    
        sort(x,x+nCount);//先排序 
        nCount=unique(x,x+nCount)-x;//合并掉相同的项 
        for(i=0;i<nCount;i++)
          hash[x[i]]=i;
        Build(1,0,nCount-1);
        int res=0;
        for(i=n-1;i>=0;i--)//要从上面开始看。 
          if(Post(1,hash[posters[i].l],hash[posters[i].r]))
            res++;
        printf("%d\n",res);
    }    
    return 0;
}

想了一天，终于解决了这题，对线段树也有了更深的认识。

也明白了离散化的本质。乘胜追击，再做几道线段树来。

by 2011-8-15

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/15/2139931.html

posted @ 2011-08-25 10:45 kuangbin 阅读(202) | 评论 (0) | 编辑收藏

[导入]ACM POJ1151 (HDU 1542) Atlantis（矩形面积并，线段树+离散化+扫描线）

Atlantis

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 9693		Accepted: 3791

Description

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input

The input consists of several test cases. Each test case starts with a line containing a single integer n (1 <= n <= 100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don't process it.

Output

For each test case, your program should output one section. The first line of each section must be "Test case #k", where k is the number of the test case (starting with 1). The second one must be "Total explored area: a", where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00

Source

Mid-Central European Regional Contest 2000

/*
POJ 1151 Atlantis
求矩形并的面积（线段树+离散化） 
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 201
struct Node
{
    int l,r;//线段树的左右整点
    int c;//c用来记录重叠情况
    double cnt,lf,rf;//
    //cnt用来计算实在的长度，rf,lf分别是对应的左右真实的浮点数端点 
}segTree[MAXN*3];     
struct Line
{
    double x,y1,y2;
    int f;
}line[MAXN];
//把一段段平行于y轴的线段表示成数组 ，
//x是线段的x坐标，y1,y2线段对应的下端点和上端点的坐标 
//一个矩形 ，左边的那条边f为1，右边的为-1，
//用来记录重叠情况，可以根据这个来计算，nod节点中的c 

bool cmp(Line a,Line b)//sort排序的函数
{
    return a.x < b.x;
}     

double y[MAXN];//记录y坐标的数组
void Build(int t,int l,int r)//构造线段树
{
    segTree[t].l=l;segTree[t].r=r;
    segTree[t].cnt=segTree[t].c=0;
    segTree[t].lf=y[l];
    segTree[t].rf=y[r];
    if(l+1==r)  return;
    int mid=(l+r)>>1;
    Build(t<<1,l,mid);
    Build(t<<1|1,mid,r);//递归构造 
}     
void calen(int t)//计算长度
{
    if(segTree[t].c>0)
    {
        segTree[t].cnt=segTree[t].rf-segTree[t].lf;
        return;
    }    
    if(segTree[t].l+1==segTree[t].r)  segTree[t].cnt=0;
    else  segTree[t].cnt=segTree[t<<1].cnt+segTree[t<<1|1].cnt;
}     
void update(int t,Line e)//加入线段e，后更新线段树
{
    if(e.y1==segTree[t].lf&&e.y2==segTree[t].rf)
    {
        segTree[t].c+=e.f;
        calen(t);
        return;
    }    
    if(e.y2<=segTree[t<<1].rf)  update(t<<1,e);
    else if(e.y1>=segTree[t<<1|1].lf)  update(t<<1|1,e);
    else
    {
        Line tmp=e;
        tmp.y2=segTree[t<<1].rf;
        update(t<<1,tmp);
        tmp=e;
        tmp.y1=segTree[t<<1|1].lf;
        update(t<<1|1,tmp);
    }    
    calen(t);
}    
int main()
{
    int i,n,t,iCase=0;
    double x1,y1,x2,y2;
    while(scanf("%d",&n),n)
    {
        iCase++;
        t=1;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[t].x=x1;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=1;
            y[t]=y1;
            t++;
            line[t].x=x2;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=-1;
            y[t]=y2;
            t++;
        } 
        sort(line+1,line+t,cmp);
        sort(y+1,y+t);   
        Build(1,1,t-1);
        update(1,line[1]);
        double res=0;
        for(i=2;i<t;i++)
        {
            res+=segTree[1].cnt*(line[i].x-line[i-1].x);
            update(1,line[i]);
        }    
        printf("Test case #%d\nTotal explored area: %.2f\n\n",iCase,res);
        //看来POJ上%.2f可以过，%.2lf却不行了 
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/16/2140544.html

posted @ 2011-08-25 10:45 kuangbin 阅读(446) | 评论 (0) | 编辑收藏

[导入]ACM HDU 1255 覆盖的面积（矩形面积交，线段树+离散化）

覆盖的面积

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1415 Accepted Submission(s): 677

Problem Description

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.

注意:本题的输入数据较多,推荐使用scanf读入数据.

Output

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.

Sample Input

2
5
1 4 2
3 3 7
1.5 5 4.5
5 1.25 7.5 4
3 10 7
3
0 1 1
0 2 1
0 3 1

Sample Output

7.63
0.00

Author

Ignatius.L & weigang Lee

Recommend

Ignatius.L

/*
HDU 1255 覆盖的面积
求矩形交的面积（线段树+离散化） 
给定一些矩形 
被这些矩形覆盖过至少两次的区域的面积
*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 2010
struct Node
{
    int l,r;//线段树的左右整点
    int c;//c用来记录重叠情况
    double lf,rf;//
    //rf,lf分别是对应的左右真实的浮点数端点 
    double cnt,more;//cnt是值被覆盖一次以上的长度，more值被覆盖两次以上的长度 
}segTree[MAXN*3];     
struct Line
{
    double x,y1,y2;
    int f;
}line[MAXN];
//把一段段平行于y轴的线段表示成数组 ，
//x是线段的x坐标，y1,y2线段对应的下端点和上端点的坐标 
//一个矩形 ，左边的那条边f为1，右边的为-1，
//用来记录重叠情况，可以根据这个来计算，nod节点中的c 

bool cmp(Line a,Line b)//sort排序的函数
{
    return a.x < b.x;
}     

double y[MAXN];//记录y坐标的数组
void Build(int t,int l,int r)//构造线段树
{
    segTree[t].l=l;segTree[t].r=r;
    segTree[t].cnt=segTree[t].c=0;
    segTree[t].lf=y[l];
    segTree[t].rf=y[r];
    if(l+1==r)  return;
    int mid=(l+r)>>1;
    Build(t<<1,l,mid);
    Build(t<<1|1,mid,r);//递归构造 
}     
void calen(int t)//计算长度
{
    if(segTree[t].c>=2)
    {
        segTree[t].more=segTree[t].cnt=segTree[t].rf-segTree[t].lf;
        return;
    }    
    else if(segTree[t].c==1)
    {
        segTree[t].cnt=segTree[t].rf-segTree[t].lf;
        if(segTree[t].l+1==segTree[t].r)  segTree[t].more=0;
        else segTree[t].more=segTree[t<<1].cnt+segTree[t<<1|1].cnt;
    }    
    else
    {
        if(segTree[t].l+1==segTree[t].r)  segTree[t].more=segTree[t].cnt=0;
        else  
        {
            segTree[t].cnt=segTree[t<<1].cnt+segTree[t<<1|1].cnt;
            segTree[t].more=segTree[t<<1].more+segTree[t<<1|1].more;
        }    
    }    
}     
void update(int t,Line e)//加入线段e，后更新线段树
{
    if(e.y1==segTree[t].lf&&e.y2==segTree[t].rf)
    {
        segTree[t].c+=e.f;
        calen(t);
        return;
    }    
    if(e.y2<=segTree[t<<1].rf)  update(t<<1,e);
    else if(e.y1>=segTree[t<<1|1].lf)  update(t<<1|1,e);
    else
    {
        Line tmp=e;
        tmp.y2=segTree[t<<1].rf;
        update(t<<1,tmp);
        tmp=e;
        tmp.y1=segTree[t<<1|1].lf;
        update(t<<1|1,tmp);
    }    
    calen(t);
}    
int main()
{
    int i,n,t,T;
    double x1,y1,x2,y2;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n); 
        t=1;
        for(i=1;i<=n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[t].x=x1;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=1;
            y[t]=y1;
            t++;
            line[t].x=x2;
            line[t].y1=y1;
            line[t].y2=y2;
            line[t].f=-1;
            y[t]=y2;
            t++;
        } 
        sort(line+1,line+t,cmp);
        sort(y+1,y+t);   
        Build(1,1,t-1);
        update(1,line[1]);
        double res=0;
        for(i=2;i<t;i++)
        {
            res+=segTree[1].more*(line[i].x-line[i-1].x);
            update(1,line[i]);
        }    
        printf("%.2lf\n",res);
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/16/2140779.html

posted @ 2011-08-25 10:45 kuangbin 阅读(475) | 评论 (0) | 编辑收藏

[导入]ACM POJ 3321 Apple Tree（树状数组）

Apple Tree

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 11282		Accepted: 3214

Description

There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.

The tree has N forks which are connected by branches. Kaka numbers the forks by 1 to N and the root is always numbered by 1. Apples will grow on the forks and two apple won't grow on the same fork. kaka wants to know how many apples are there in a sub-tree, for his study of the produce ability of the apple tree.

The trouble is that a new apple may grow on an empty fork some time and kaka may pick an apple from the tree for his dessert. Can you help kaka?

Input

The first line contains an integer N (N ≤ 100,000) , which is the number of the forks in the tree.
The following N - 1 lines each contain two integers u and v, which means fork u and fork v are connected by a branch.
The next line contains an integer M (M ≤ 100,000).
The following M lines each contain a message which is either
"C x" which means the existence of the apple on fork x has been changed. i.e. if there is an apple on the fork, then Kaka pick it; otherwise a new apple has grown on the empty fork.
or
"Q x" which means an inquiry for the number of apples in the sub-tree above the fork x, including the apple (if exists) on the fork x
Note the tree is full of apples at the beginning

Output

For every inquiry, output the correspond answer per line.

Sample Input

Sample Output

3
2

Source

POJ Monthly--2007.08.05, Huang, Jinsong

/**************************************************
POJ 3321  Apple Tree
一棵树上长了苹果，每一个树枝节点上有长苹果和不长苹果两种状态，
两种操作，一种操作能够改变树枝上苹果的状态，
另一种操作询问某一树枝节点一下的所有的苹果有多少。具体做法
是做一次dfs，记下每个节点的开始时间Start[i]和结束时间End[i]，
那么对于i节点的所有子孙的开始时间和结束时间都应位于Start[i]
和End[i]之间，另外用一个数组C[i]记录附加在节点i上的苹果的个数，
然后用树状数组统计Start[i]到End[i]之间的附加苹果总数。这里
用树状数组统计区间可以用Sum(Start[i])-Sum(End[i]-1)来计算。 

***************************************************/
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
#define MAXN 220000
int C[MAXN];
typedef vector<int> VCT_INT;
vector<VCT_INT>G(MAXN/2);
int Lowbit[MAXN];
int Start[MAXN];//dfs的开始时间 
int End[MAXN];//dfs的结束时间 
bool HasApple[MAXN/2];
int nCount;
void Dfs(int v)
{
    Start[v]=++nCount;
    for(int i=0;i<G[v].size();i++)
       Dfs(G[v][i]);
    End[v]=++nCount;
}  
int QuerySum(int p)
{
    int nSum=0;
    while(p>0)
    {
        nSum+=C[p];
        p-=Lowbit[p];
    }    
    return nSum;
}    
void Modify(int p,int val)
{
    while(p<=nCount)
    {
        C[p]+=val;
        p+=Lowbit[p];
    }    
} 
int main()
{
    int n;
    scanf("%d",&n);
    int x,y;
    int i,j,k;
    //建图 
    for(i=0;i<n-1;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
    }    
    nCount=0;
    Dfs(1);
    //树状数组要处理的原始数组下标范围1--nCount 
    for(i=1;i<=nCount;i++)
    {
        Lowbit[i]=i&(i^(i-1));
    }    
    for(i=1;i<=n;i++)
      HasApple[i]=1;
    int m;
    //求C数组 
    for(i=1;i<=nCount;i++)
      C[i]=i-(i-Lowbit[i]+1)+1;
    scanf("%d",&m);
    for(i=0;i<m;i++)
    {
        char cmd[10];
        int a;
        scanf("%s%d",cmd,&a);
        if(cmd[0]=='C')
        {
            if(HasApple[a])
            {
                Modify(Start[a],-1);
                Modify(End[a],-1);
                HasApple[a]=0;
            }    
            else
            {
                Modify(Start[a],1);
                Modify(End[a],1);
                HasApple[a]=1;
            }    
        }
        else
        {
            int t1=QuerySum(End[a]);
            int t2=QuerySum(Start[a]);
            printf("%d\n",(t1-t2)/2+HasApple[a]);
        }        
    }
    return 0;
        
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/16/2141607.html

posted @ 2011-08-25 10:45 kuangbin 阅读(234) | 评论 (0) | 编辑收藏

[导入]【转】2-SAT问题及其算法

摘要: 原文地址：http://www.cppblog.com/MatoNo1/archive/2011/07/13/150766.aspx 为了便于查看，只有转载下来了，免得找不到了【2-SAT问题】现有一个由N个布尔值组成的序列A，给出一些限制关系，比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等，要确定A[0..N-1]的值，使得... 阅读全文

posted @ 2011-08-25 10:45 kuangbin 阅读(146) | 评论 (0) | 编辑收藏

[导入]ACM POJ 3648 Wedding（2-SAT入门）

题目链接：http://poj.org/problem?id=3648

本文作者：kuangbin

（转载请注明出处，博客：www.cnblogs.com/kuangbin)

【题目大意】很多对夫妇参加一对新人的婚礼。分别做在长桌子的两侧。新郎、新娘分别坐两侧，新娘只能看到她对面的人。新娘不想看到她对面有夫妇。

而且有一些人是有通奸关系的（男的和男的有，女的和男的、女的和女的都可能有，而且新郎也可能和别人有通奸关系），新娘不想看到有通奸关系一对人。

也就是有通奸关系的不能一起坐在新娘对面。

输入是：_n对夫妇（包括新郎新娘在女的，编号为0-(n-1)，新郎、新娘那一对的编号为0）,_m对通奸关系。

接下来_m行有通奸关系的。h表示男的，w表是女的，3w 5h即表示第三对夫妇的女的和第五对夫妇的男的有不寻常关系。

【题目类别】2-SAT

【题目分析】题目就是需要选出包括新郎在内的一半人坐在新娘对面去，选出来的人不能有夫妇，不能有通奸关系的一对人。

编号分别为0-2*_n，奇数是男的，偶数是女的。自然0是新娘，1是新郎了。

为了一定选到1，可以加一条边0->1,这样选了新娘就必定会选当新郎，从而判断错误。这样如果有符合题意的_n个人选出来，

则选出来的肯定包括新郎了。

注意的是输出的时候是输出和新娘坐同一边的人。即反过来输出就可以了；

代码：

/*
POJ3648
求字典序最小的解 
*/
#include<iostream>
#include<stdio.h>
using namespace std;
const int MAXN=20000;
const int MAXM=100000;//这个必须开大一点 
struct Node
{
    int a,b,pre,next;
}E[MAXM],E2[MAXM];//原图和逆图 
int _n,n,m,V[MAXN],ST[MAXN][2],Q[MAXN],Q2[MAXN],vst[MAXN];
bool res_ex;
void init_d()//初始化 
{
    for(int i=0;i<n;i++)//相当于建出双重邻接表的头结点 
       E[i].a=E[i].pre=E[i].next=E2[i].a=E2[i].pre=E2[i].next=i;
    m=n;//m是建造双重邻接表时结点的编号 
}     
void add_edge(int a,int b)//加入边(a,b),需要在原图和逆图中添加边 
{//实际上建造出的是循环状的图 
    E[m].a=a;E[m].b=b;E[m].pre=E[a].pre;E[m].next=a;E[a].pre=m;E[E[m].pre].next=m;
    E2[m].a=b;E2[m].b=a;E2[m].pre=E2[b].pre;E2[m].next=b;E2[b].pre=m;E2[E2[m].pre].next=m++;
} 
void solve()
{
    for(int i=0;i<n;i++)
    {
        V[i]=0;
        vst[i]=0;
    }    
    res_ex=1;
    int i,i1,i2,j,k,len,front,rear,front2,rear2;
    bool ff;
    for(int _i=0;_i<_n;_i++)
    {
        if(V[_i<<1]==1||V[(_i<<1)+1]==1)  continue;//找一对未被确定的点 
        i=_i<<1;len=0;
        if(!V[i])
        {
            ST[len][0]=i;ST[len++][1]=1;
            if(!V[i ^ 1])
            {
                ST[len][0]=i^1;
                ST[len++][1]=2;
            }   
            Q[front=rear=0]=i;
            vst[i]=i1=n+i;
            Q2[front2=rear2=0]=i^1;
            vst[i^1]=i2=(n<<1)+i;
            //i1,i2为标志量，这样设置标志量使得每次都不一样，省去了初始化 
            ff=1;
            for(;front<=rear;front++)
            {
                j=Q[front];
                for(int p=E[j].next;p!=j;p=E[p].next)
                {
                    k=E[p].b;
                    if(V[k]==2||vst[k]==i2||V[k^1]==1||vst[k^1]==i1)
                    {ff=0;break;}
                    if(vst[k]!=i1)
                    {
                        Q[++rear]=k;vst[k]=i1;
                        if(!V[k])
                        {
                            ST[len][0]=k;
                            ST[len++][1]=1;
                        }    
                    }    
                    if(vst[k^1]!=i2)
                    {
                        Q2[++rear2]=k^1;vst[k^1]=i2;
                        if(!V[k])
                        {
                            ST[len][0]=k^1;
                            ST[len++][1]=2;
                        }    
                    }    
                }  
                if(!ff) break;  
            }   
            if(ff)
            {
                for(;front2<=rear2;front2++)
                {
                    j=Q2[front2];
                    for(int p=E2[j].next;p!=j;p=E2[p].next)
                    {
                        k=E2[p].b;
                        if(V[k]==1||vst[k]==i1)
                        {
                            ff=0;
                            break;
                        }    
                        if(vst[k]!=i2)
                        {
                            vst[k]=i2;Q2[++rear]=k;
                            if(!V[k])
                            {
                                ST[len][0]=k;
                                ST[len++][1]=2;
                            }    
                        }    
                    } 
                    if(!ff) break;   
                } 
                if(ff)
                {
                    for(int j=0;j<len;j++) V[ST[j][0]]=ST[j][1];
                    continue;
                }       
            }      
        } 
        i=(_i<<1)+1;len=0;
        if(!V[i])
        {
            ST[len][0]=i;ST[len++][1]=1;
            if(!V[i ^ 1])
            {
                ST[len][0]=i^1;
                ST[len++][1]=2;
            }   
            Q[front=rear=0]=i;
            vst[i]=i1=n+i;
            Q2[front2=rear2=0]=i^1;
            vst[i^1]=i2=(n<<1)+i;
            ff=1;
            for(;front<=rear;front++)
            {
                j=Q[front];
                for(int p=E[j].next;p!=j;p=E[p].next)
                {
                    k=E[p].b;
                    if(V[k]==2||vst[k]==i2||V[k^1]==1||vst[k^1]==i1)
                    {ff=0;break;}
                    if(vst[k]!=i1)
                    {
                        Q[++rear]=k;vst[k]=i1;
                        if(!V[k])
                        {
                            ST[len][0]=k;
                            ST[len++][1]=1;
                        }    
                    }    
                    if(vst[k^1]!=i2)
                    {
                        Q2[++rear2]=k^1;vst[k^1]=i2;
                        if(!V[k])
                        {
                            ST[len][0]=k^1;
                            ST[len++][1]=2;
                        }    
                    }    
                }  
                if(!ff) break;  
            }   
            if(ff)
            {
                for(;front2<=rear2;front2++)
                {
                    j=Q2[front2];
                    for(int p=E2[j].next;p!=j;p=E2[p].next)
                    {
                        k=E2[p].b;
                        if(V[k]==1||vst[k]==i1)
                        {
                            ff=0;
                            break;
                        }    
                        if(vst[k]!=i2)
                        {
                            vst[k]=i2;Q2[++rear]=k;
                            if(!V[k])
                            {
                                ST[len][0]=k;
                                ST[len++][1]=2;
                            }    
                        }    
                    } 
                    if(!ff) break;   
                } 
                if(ff)
                {
                    for(int j=0;j<len;j++) V[ST[j][0]]=ST[j][1];
                    continue;
                }       
            }      
        } 
        if(V[_i<<1]+V[(_i<<1)+1]!=3){res_ex=0;break;}   
    }    
}
int main()
{
    int _m,a,b;
    char ch1,ch2;
    while(scanf("%d%d",&_n,&_m)!=EOF)//_n是点的对数，_m是冲突的点个数 
    {
        if(_n==0&&_m==0)break;
        n=_n<<1;
        init_d();
        for(int i=0;i<_m;i++)
        {
            scanf("%d%c%d%c",&a,&ch1,&b,&ch2);
            if(ch1=='w')  a=2*a;
            else a=2*a+1;
            if(ch2=='w')  b=2*b;
            else  b=2*b+1;
            if(a!=(b^1))
            {
                add_edge(a,b^1);//选a,必选b^1， 
                add_edge(b,a^1);//选b,必选a^1， 
            }    
        }
        add_edge(0,1);//加一条新娘到新郎的边。
        //表示选了新娘必选新郎，这样如果选了新娘就会判断无解。
        //这样选出来的组合必定是有新郎的，即和新郎坐在同一侧的 
        solve();
        bool first=false;
        if(res_ex)
        {
            for(int i=0;i<n;i++)
            {
              if(V[i]==1&&i!=1)
              {
                  if(first)printf(" ");
                  else first=true;
                  printf("%d%c",i/2,i%2==0?'h':'w');//选取的是和新郎同一侧的，输出和新娘同一侧的
                                             //所以输出的时候h和w换一下 
              }    
            }  
            printf("\n");  
        }    
        else printf("bad luck\n");    
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/22/2149667.html

posted @ 2011-08-25 10:45 kuangbin 阅读(169) | 评论 (0) | 编辑收藏

[导入]ACM HDU 3622 Bomb Game(2-SAT）

Bomb Game

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1543 Accepted Submission(s): 492

Problem Description

Robbie is playing an interesting computer game. The game field is an unbounded 2-dimensional region. There are N rounds in the game. At each round, the computer will give Robbie two places, and Robbie should choose one of them to put a bomb. The explosion area of the bomb is a circle whose center is just the chosen place. Robbie can control the power of the bomb, that is, he can control the radius of each circle. A strange requirement is that there should be no common area for any two circles. The final score is the minimum radius of all the N circles.
Robbie has cracked the game, and he has known all the candidate places of each round before the game starts. Now he wants to know the maximum score he can get with the optimal strategy.

Input

The first line of each test case is an integer N (2 <= N <= 100), indicating the number of rounds. Then N lines follow. The i-th line contains four integers x_1i, y_1i, x_2i, y_2i, indicating that the coordinates of the two candidate places of the i-th round are (x_1i, y_1i) and (x_2i, y_2i). All the coordinates are in the range [-10000, 10000].

Output

Output one float number for each test case, indicating the best possible score. The result should be rounded to two decimal places.

Sample Input

Sample Output

1.41
1.00

Source

The 35th ACM/ICPC Asia Regional Tianjin Site —— Online Contest

Recommend

lcy

题意:给n对炸弹可以放置的位置(每个位置为一个二维平面上的点),每次放置炸弹是时只能选择这一对中的其中一个点,每个炸弹爆炸的范围半径都一样,控制爆炸的半径使得所有的爆炸范围都不相交(可以相切),求解这个最大半径.
首先二分最大半径值,然后2-sat构图判断其可行性,对于每两队位置(u,uu)和(v,vv),如果u和v之间的距离小于2*id,也就是说位置u和位置v处不能同时防止炸弹(两范围相交),所以连边(u,vv)和(v,uu),求解强连通分量判断可行性.

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN=205;
const int MAXM=40005;
#define eps 1e-4
struct Node
{
    int x,y;
}s[MAXN];
struct Node1
{
    int from,to,next;
}edge1[MAXM],edge2[MAXM];
int visit1[MAXN],visit2[MAXN],head1[MAXN],head2[MAXN],Belong[MAXN],T[MAXN];
int tol1,tol2,Bcnt,Tcnt;
void add(int a,int b)
{
    edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
    edge2[tol2].from=b;edge2[tol2].to=a;edge2[tol2].next=head2[b];head2[b]=tol2++;
} 
void dfs1(int x)
{
    int j;
    visit1[x]=1;
    for(j=head1[x];j!=-1;j=edge1[j].next)
       if(visit1[edge1[j].to]==0)  dfs1(edge1[j].to);
    T[Tcnt++]=x;
}           
void dfs2(int x)
{
    int j;
    visit2[x]=1;
    Belong[x]=Bcnt;
    for(j=head2[x];j!=-1;j=edge2[j].next)
       if(visit2[edge2[j].to]==0)  dfs2(edge2[j].to);
}       
double dist(int x1,int y1,int x2,int y2)
{
    return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}    
int main()
{
    int i,j,n,ans;
    double left,right,mid,Max,ans1;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&s[2*i].x,&s[2*i].y,&s[2*i+1].x,&s[2*i+1].y);
        }    
        right=20000*sqrt(2.0);
        left=0;
        Max=0;
        while(right-left>=eps)
        {
            mid=(right+left)/2;
            for(i=0;i<2*n;i++)
            {
                head1[i]=-1;
                head2[i]=-1;
                visit1[i]=0;
                visit2[i]=0;
            }    
            tol1=tol2=Bcnt=Tcnt=0;
            for(i=0;i<2*n-2;i++)
            {
                if(i%2==1)  ans=i+1;
                else ans=i+2;
                for(j=ans;j<2*n;j++)
                {
                    ans1=dist(s[i].x,s[i].y,s[j].x,s[j].y);
                    if(ans1<2*mid)
                    {
                        add(i,j^1);
                        add(j,i^1);   
                    }    
                }    
            }    
            for(i=0;i<2*n;i++)
                if(visit1[i]==0)  dfs1(i);
            for(i=Tcnt-1;i>=0;i--)
            {
                if(visit2[T[i]]==0)
                {
                    dfs2(T[i]);
                    Bcnt++;
                }    
            }    
            for(i=0;i<=2*n-2;i+=2)
            {
                if(Belong[i]==Belong[i+1])break;
            }    
            if(i<=2*n-2) right=mid-eps;//可以不减 
            else
            {
                Max=mid;
                left=mid+eps;//可以不加eps 
            }    
        }    
        printf("%.2lf\n",Max);
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/22/2149936.html

posted @ 2011-08-25 10:45 kuangbin 阅读(247) | 评论 (0) | 编辑收藏

[导入]ACM HDU 3715 Go Deeper

Go Deeper

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 309 Accepted Submission(s): 122

Problem Description

Here is a procedure's pseudocode:

go(int dep, int n, int m)
begin
output the value of dep.
if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
end

In this code n is an integer. a, b, c and x are 4 arrays of integers. The index of array always starts from 0. Array a and b consist of non-negative integers smaller than n. Array x consists of only 0 and 1. Array c consists of only 0, 1 and 2. The lengths of array a, b and c are m while the length of array x is n. Given the elements of array a, b, and c, when we call the procedure go(0, n, m) what is the maximal possible value the procedure may output?

Input

There are multiple test cases. The first line of input is an integer T (0 < T ≤ 100), indicating the number of test cases. Then T test cases follow. Each case starts with a line of 2 integers n and m (0 < n ≤ 200, 0 < m ≤ 10000). Then m lines of 3 integers follow. The i-th(1 ≤ i ≤ m) line of them are a_i-1 ,b_i-1 and c_i-1 (0 ≤ a_i-1, b_i-1 < n, 0 ≤ c_i-1 ≤ 2).

Output

For each test case, output the result in a single line.

Sample Input

Sample Output

1
1
2

Author

CAO, Peng

Source

The 2010 ACM-ICPC Asia Chengdu Regional Contest

Recommend

zhouzeyong

#include<stdio.h>
#include<string.h>
#define MAXN 405
#define MAXM 160010
struct Node
{
    int from,to,next;
}edge1[MAXM],edge2[MAXM];
struct Node1
{
    int a,b,c;
}s[MAXM];
int n,m,head1[MAXN],head2[MAXN],visit1[MAXN],visit2[MAXN],tol1,tol2;
int Tcnt,Bcnt,Belong[MAXN],T[MAXN];
void add(int a,int b)
{
    edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
    edge2[tol2].from=b;edge2[tol2].to=a;edge2[tol2].next=head2[b];head2[b]=tol2++;
}    
void dfs1(int i)
{
    int j,u;
    visit1[i]=1;
    for(j=head1[i];j!=-1;j=edge1[j].next)
    {
        u=edge1[j].to;
        if(!visit1[u])  dfs1(u);
    }    
    T[Tcnt++]=i;
}  
void dfs2(int i)
{
    int j,u;
    visit2[i]=1;
    Belong[i]=Bcnt;
    for(j=head2[i];j!=-1;j=edge2[j].next)
    {
        u=edge2[j].to;
        if(!visit2[u])  dfs2(u);
    }    
} 
int main()
{
    int i,ans,right,left,mid,ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
           scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
        left=0;
        right=m;
        while(left<=right)
        {
            mid=(left+right)/2;
            for(i=0;i<2*n;i++)
            {
                head1[i]=-1;
                head2[i]=-1;
                visit1[i]=0;
                visit2[i]=0;
            }  
            tol1=tol2=0;
            Tcnt=Bcnt=0;
            for(i=0;i<mid;i++)
            {
                if(s[i].c==0)
                {
                    add(s[i].a,s[i].b+n);
                    add(s[i].b,s[i].a+n);
                }    
                else if(s[i].c==1)
                {
                    add(s[i].a,s[i].b);
                    add(s[i].b,s[i].a);
                    add(s[i].a+n,s[i].b+n);
                    add(s[i].b+n,s[i].a+n);
                }    
                else if(s[i].c==2)
                {
                    add(s[i].a+n,s[i].b);
                    add(s[i].b+n,s[i].a);
                }    
            }
            for(i=0;i<2*n;i++)
               if(!visit1[i])  dfs1(i);      
            for(i=Tcnt-1;i>=0;i--)
            {
                if(!visit2[T[i]])
                {
                    dfs2(T[i]);
                    Bcnt++;
                }    
            }    
            for(i=0;i<n;i++)
            {
                if(Belong[i]==Belong[i+n]) break;
            }    
            if(i==n)
            {
                ans=mid;left=mid+1;
            }    
            else  right=mid-1;
        }    
        printf("%d\n",ans);
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/22/2150058.html

posted @ 2011-08-25 10:45 kuangbin 阅读(171) | 评论 (0) | 编辑收藏

[导入]POJ 3207 Ikki's Story IV - Panda's Trick（2-SAT入门）

讲解见：http://hi.baidu.com/chinaeli/blog/item/dd00463cdb40eecf9f3d62c7.html

http://blog.163.com/lfw2565295@126/blog/static/12200516201102012251212/

代码：

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN=1005;
const int MAXM=1000005;
struct Node
{
    int l,r;
}e[MAXN];
struct Node1
{
    int from,to,next;
}edge1[MAXM],edge2[MAXM];
int visit1[MAXN],visit2[MAXN],head1[MAXN],head2[MAXN],Belong[MAXN],T[MAXN];
int tol1,tol2,Bcnt,Tcnt;
void add(int a,int b)
{
    edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
    edge2[tol2].from=b;edge2[tol2].to=a;edge2[tol2].next=head2[b];head2[b]=tol2++;
} 
void dfs1(int x)
{
    int j;
    visit1[x]=1;
    for(j=head1[x];j!=-1;j=edge1[j].next)
       if(visit1[edge1[j].to]==0)  dfs1(edge1[j].to);
    T[Tcnt++]=x;
}           
void dfs2(int x)
{
    int j;
    visit2[x]=1;
    Belong[x]=Bcnt;
    for(j=head2[x];j!=-1;j=edge2[j].next)
       if(visit2[edge2[j].to]==0)  dfs2(edge2[j].to);
}       
double dist(int x1,int y1,int x2,int y2)
{
    return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}    
int main()
{
    int i,j,n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&e[i].l,&e[i].r);
            /*if(e[i].l>e[i].r)
            {
                int tmp=e[i].l;
                e[i].l=e[i].r;
                e[i].r=e[i].l;
            }  */  //这个可以不加上去 
        }    
        for(i=0;i<2*m;i++)
        {
                head1[i]=-1;
                head2[i]=-1;
                visit1[i]=0;
                visit2[i]=0;
        }    
        tol1=tol2=Bcnt=Tcnt=0;
        for(i=0;i<m;i++)
           for(j=i+1;j<m;j++)
           {
               if((e[i].l<e[j].l&&e[j].l<e[i].r&&e[i].r<e[j].r)||(e[j].l<e[i].l&&e[i].l<e[j].r&&e[j].r<e[i].r))
               {
                   add(2*i,2*j+1);
                   add(2*j+1,2*i);
                   add(2*j,2*i+1);
                   add(2*i+1,2*j);
               }    
           }    
        for(i=0;i<2*m;i++)
             if(visit1[i]==0)  dfs1(i);
        for(i=Tcnt-1;i>=0;i--)
        {
                if(visit2[T[i]]==0)
                {
                    dfs2(T[i]);
                    Bcnt++;
                }    
        }    
        for(i=0;i<=2*m-2;i+=2)
        {
                if(Belong[i]==Belong[i+1])break;
        }    
        if(i>2*m-2) printf("panda is telling the truth...\n");
        else
          printf("the evil panda is lying again\n");

    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/23/2150098.html

posted @ 2011-08-25 10:45 kuangbin 阅读(160) | 评论 (0) | 编辑收藏

ACM POJ 2723 Get Luffy Out（2-SAT入门）

题目链接：http://poj.org/problem?id=2723

【题目大意】

有2n把钥匙，分成2组，给你每组的钥匙信息，并且每组的钥匙只能用一个。

有m个门，每个门有2个锁，只要打开一个锁这个门就开了。（顺序遇见m个门）

问你最多能够打开多少个门。

【解题思路】

因为只能门只能按照顺序打开，所以很自然二分是个很好的选择。
建图的依据：
１、每对钥匙a,b有(a->!b),(b->!a) 也就是 a and b = 0　a被用b不被用，或b被用a不被用，或a,b都不被用
２、每善门对应锁的钥匙a,b有(!a->b),(!b->a) 也就是 a or b = 1，用a能打开用b不能打开，或用b能打开用a不能打开，或用a能打开用b也能打开

用二分法求解：

我下面用了两种方法求解的，时间都差不多。也就是求解强连通分量的两种方法。

/*
POJ  2723 Get Luffy Out
AC代码 
*/

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN=1<<12;
const int MAXM=1<<24;
struct Node
{
    int l,r;
}e[MAXN];
struct Node1
{
    int from,to,next;
}edge1[MAXM],edge2[MAXM];
int visit1[MAXN],visit2[MAXN],head1[MAXN],head2[MAXN],Belong[MAXN],T[MAXN];
int tol1,tol2,Bcnt,Tcnt;
int hash[MAXN];
void add(int a,int b)
{
    edge1[tol1].from=a;edge1[tol1].to=b;edge1[tol1].next=head1[a];head1[a]=tol1++;
    edge2[tol2].from=b;edge2[tol2].to=a;edge2[tol2].next=head2[b];head2[b]=tol2++;
} 
void dfs1(int x)
{
    int j;
    visit1[x]=1;
    for(j=head1[x];j!=-1;j=edge1[j].next)
       if(visit1[edge1[j].to]==0)  dfs1(edge1[j].to);
    T[Tcnt++]=x;
}           
void dfs2(int x)
{
    int j;
    visit2[x]=1;
    Belong[x]=Bcnt;
    for(j=head2[x];j!=-1;j=edge2[j].next)
       if(visit2[edge2[j].to]==0)  dfs2(edge2[j].to);
}       
int main()
{
    int i,j,n,m;
    int right,left,mid,ans;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        
        if(n==0&&m==0)break;
        int a,b;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            hash[a]=b;
            hash[b]=a;
        }       
        for(i=0;i<m;i++)
           scanf("%d%d",&e[i].l,&e[i].r);
        left=0;
        right=m;
        while(left<=right)
        {
            mid=(left+right)/2;
            for(i=0;i<4*n;i++)
            {
                head1[i]=-1;
                head2[i]=-1;
                visit1[i]=0;
                visit2[i]=0;
            }  
            tol1=tol2=0;
            Tcnt=Bcnt=0;
            for(i=0;i<2*n;i++)
            {
                add(i,hash[i]+2*n);
            }    
            for(i=0;i<mid;i++)
            {
                  
                if(e[i].l!=e[i].r)
                {
                    add(e[i].l+2*n,e[i].r);
                    add(e[i].r+2*n,e[i].l);
                }    
                if(e[i].l==e[i].r)
                {
                    add(e[i].l+2*n,e[i].l);
                }        
                   
            }
            for(i=0;i<4*n;i++)
               if(!visit1[i])  dfs1(i);      
            for(i=Tcnt-1;i>=0;i--)
            {
                if(!visit2[T[i]])
                {
                    dfs2(T[i]);
                    Bcnt++;
                }    
            }    
            for(i=0;i<2*n;i++)
            {
                if(Belong[i]==Belong[i+2*n]) break;
            }    
            if(i>=2*n)
            {
                ans=mid;left=mid+1;
            }    
            else  right=mid-1;
        }    
        printf("%d\n",ans);
    }    
    return 0;
}

/*
POJ  2723 Get Luffy Out
AC代码 
*/
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN=1<<12;
const int MAXM=1<<24;
int n,m;
struct Node
{
    int l,r;
}e[MAXN];
struct Node1
{
    int from,to,next;
}edge[MAXM];
int ecnt;
int head[MAXN],Belong[MAXN],Stack[MAXN];
int top,idx,b_cnt;
int hash[MAXN];
int DFN[MAXN],LOW[MAXN];
bool Instack[MAXN];
void add(int a,int b)
{
    edge[ecnt].from=a;edge[ecnt].to=b;edge[ecnt].next=head[a];head[a]=ecnt++;
   
} 
void Tarjan(int u)
{
    int i,v;
    DFN[u]=LOW[u]=(++idx);
    Stack[++top]=u;
    Instack[u]=true;
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].to;
        if(!DFN[v])
        {
            Tarjan(v);
            if(LOW[u]>LOW[v])LOW[u]=LOW[v];
        }    
        else if(Instack[v]&&LOW[u]>DFN[v])
           LOW[u]=DFN[v];
    }
    if(LOW[u]==DFN[u])
    {
        b_cnt++;
        do
        {
            v=Stack[top--];
            Instack[v]=false;
            Belong[v]=b_cnt;
        }while(u!=v);   
    }        
    
}      
int solve()
{
    int i;
    b_cnt=idx=top=0;
    for(i=0;i<4*n;i++)
    {
        DFN[i]=LOW[i]=0;
        Belong[i]=0;
        Instack[i]=false;
    }    
    for(i=0;i<4*n;i++)
       if(!DFN[i])  Tarjan(i);
    for(i=0;i<2*n;i++)
    {
        if(Belong[i]==Belong[i+2*n])
         return 0;
    }    
    return 1;
}        
int main()
{
    int i,j;
    int right,left,mid,ans;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        
        if(n==0&&m==0)break;
        int a,b;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            hash[a]=b;
            hash[b]=a;
        }       
        for(i=0;i<m;i++)
           scanf("%d%d",&e[i].l,&e[i].r);
        left=0;
        right=m;
        while(left<=right)
        {
            mid=(left+right)/2;
            for(i=0;i<4*n;i++)
            {
                head[i]=-1;
            }  
            ecnt=0;
            for(i=0;i<2*n;i++)
            {
                add(i,hash[i]+2*n);
            }    
            for(i=0;i<mid;i++)
            {
                  
                if(e[i].l!=e[i].r)
                {
                    add(e[i].l+2*n,e[i].r);
                    add(e[i].r+2*n,e[i].l);
                }    
                if(e[i].l==e[i].r)
                {
                    add(e[i].l+2*n,e[i].l);
                }        
                   
            }
            
            if(solve())
            {
                ans=mid;left=mid+1;
            }    
            else  right=mid-1;
        }    
        printf("%d\n",ans);
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/08/24/2152038.html

posted @ 2011-08-25 10:45 kuangbin 阅读(328) | 评论 (0) | 编辑收藏

覆盖的面积

Bomb Game

Go Deeper

公告

导航

统计

常用链接

留言簿

随笔分类

随笔档案

博客

搜索

最新评论

阅读排行榜

评论排行榜