題目鏈接：http://poj.org/problem?id=2528
類型：線段樹+離散化。
本文作者：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個區間。對各個區間編號，就是離散化。然后建數。
其實浮點數也是一樣離散化的。
還有好多需要注意的地方。這題的線段樹要四倍的，普通的三倍不行了。
細節決定成?。?/span>
程序：
/*
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
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
/*
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
覆蓋的面積
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 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1
Sample Output
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
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
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
Source
/**************************************************
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
摘要: 原文地址：http://m.shnenglu.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]的值，使得... 閱讀全文
題目鏈接：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
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 x1i, y1i, x2i, y2i, indicating that the coordinates of the two candidate places of the i-th round are (x1i, y1i) and (x2i, y2i). 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
2
1 1 1 -1
-1 -1 -1 1
2
1 1 -1 -1
1 -1 -1 1
Sample Output
Source
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
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 ai-1 ,bi-1 and ci-1 (0 ≤ ai-1, bi-1 < n, 0 ≤ ci-1 ≤ 2).
Output
For each test case, output the result in a single line.
Sample Input
3
2 1
0 1 0
2 1
0 0 0
2 2
0 1 0
1 1 2
Sample Output
Author
CAO, Peng
Source
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
講解見：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
題目鏈接：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
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 31 | 1 | 2 | 3 | 4 | 5 | 6 | | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | 14 | 15 | 16 | 17 | 18 | 19 | 20 | | 21 | 22 | 23 | 24 | 25 | 26 | 27 | | 28 | 29 | 30 | 31 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
導航
統計
- 隨筆： 100
- 文章： 0
- 評論： 2
- 引用： 0
常用鏈接
留言簿(2)
隨筆分類
隨筆檔案
博客
搜索
最新評論
閱讀排行榜
評論排行榜
|
|