wust oj 1318 区间的连通性（贪心）_综合

[Submit][Status][Web Board]

Description

题目包含多组数据，你有一个集合，该集合的元素为形如(x,y)的区间，两个区间1:(a，b)、2:(c，d)，如果c<a<d 或者 c<b<d说明1号区间能到达2号区间，当然如果2号区间能到3号区间的话，那么1号区间也能到达3号区间。（该性质具有传递性）

现在给你n个操作，操作分为两种：

1.“1 x y”（x<y），将区间加入集合中。（区间按照加入的顺序编号）

2.“2 a b”（a！=b），问你第a个区间能否到达第b个区间。

Input

首先是一个n（1<=n<=200)，表示操作数，然后有n行，每行有三个数，代表一个操作。

输入保证数据都在10^9的范围内。

Output

第2种操作时，如果a能到达b，输出“YES”，否则输出“NO”（不带引号）。

Sample Input

Sample Output

NO
YES

【题解】区间合并的题，不过不用线段树，普通的标记就可以，，详解见代码注释。

【AC代码】

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int vis[205][205];struct tree
{int a,b;
}node[205];int main()
{int t,a,b,c;while(~scanf("%d",&t)){int k=1;memset(node,0,sizeof(node));memset(vis,0,sizeof(vis));for(int i=0;i<t;++i){scanf("%d%d%d",&a,&b,&c);if(a==1){node[k].a=b;node[k].b=c;for(int j=1;j<k;++j){if(b>node[j].a && b<node[j].b || c>node[j].a && c<node[j].b)//如果区间b,c的端点有一个和其他区间相重叠  则可从这个区间到其他区间vis[k][j]=1;//当前区间和j区间可达if(b<node[j].a && c>node[j].a || b<node[j].b && c>node[j].b)//同上vis[j][k]=1;}k++;}else{if(vis[b][c]) printf("YES\n");//若区间可达else{for(int j=1;j<k;++j){for(int h=1;h<k;++h)for(int l=1;l<k;++l)if(vis[h][j] && vis[j][l])//间接连通vis[h][l]=1;//也可达}if(vis[b][c]) printf("YES\n");else printf("NO\n");}}}}return 0;
}