Luogu4700 CEOI2011 Traffic Tarjan、搜索
2024-08-28 08:24:26
题意:给出平面上$N$个点,它们一定在左下角为$(0,0)$,右上角为$(A,B)$的一个矩形内的整点上(包括边界),而且会给出$M$条呈直线的边,其中有有向边也有无向边,保证任意两条边不会在非顶点处相交。现在我们定义横坐标为$0$的点为在西边的点,横坐标为$A$的点为在东边的点,现在请求出每一个在西边的点都能通过给出的边到达多少在东边的点。$N \leq 3 \times 10^5 , M \leq 9 \times 10^5 , 1 \leq A , B , \text{点的坐标} \leq 10^9$
其实还是挺考验思维的
首先一看到这道题:诶这不是裸的$tarjan$套记搜吗,然后打完发现会算重很多东西,样例都过不了qwq。
其实题目中有一句话十分隐蔽:保证任意两条边不会在非顶点处相交,这会给我们什么信息呢?
直接讲结论:除了无法到达的点,每一个西边的能够到达的东边的点都会对应纵坐标的一段区间,也就是说一定是从上往下一段连续的点,而如果其中有无法到达的点,那么一定是所有的西边的点都无法到达它。这个结论与引水入城的思想十分类似。所以我们可以先缩点,然后在剩下的$DAG$上进行记忆化搜索,把每一个西边的点能够到达的东边的点对应的区间记录下来(显然这个是很好记录的,只要记录两个端点即可),然后再去检索是否有无法到达且在这一段区间内的东边的点,将其扣除即可。
关于下面的代码,思想与上面一致,只是为了易于统计答案,将所有的边都取反,然后统计每一个东边的点能够影响的西边的点的区间,然后用前缀和获得每一个西边节点的答案,最后去看每一个西边的点对应的强连通分量是否被到达过(没有就表示没有东边的点可以到达它,自然答案就是$0$)
#include<bits/stdc++.h> using namespace std; inline int read(){ ; ; char c = getchar(); while(c != EOF && !isdigit(c)){ if(c == '-') f = ; c = getchar(); } while(c != EOF && isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return f ? -a : a; } ; struct Edge{ int end , upEd; }Ed[MAXN * ] , newEd[MAXN * ]; struct node{ int y , ind; }now[MAXN]; ][MAXN] , ind[MAXN] , num[MAXN] , s[MAXN] , dfn[MAXN] , low[MAXN]; int N , M , A , B , cntEd , cntNode , ts , headS , cntNewEd , cntSCC; bool vis[MAXN] , ins[MAXN] , ine[MAXN]; queue < int > q; inline void addEd(Edge* Ed , int* head , int& cntEd , int a , int b){ Ed[++cntEd].end = b; Ed[cntEd].upEd = head[a]; head[a] = cntEd; } void tarjan(int x){ dfn[x] = low[x] = ++ts; vis[x] = ins[x] = ; s[++headS] = x; for(int i = head[x] ; i ; i = Ed[i].upEd){ if(!vis[Ed[i].end]) tarjan(Ed[i].end); else if(!ins[Ed[i].end]) continue; low[x] = min(low[Ed[i].end] , low[x]); } if(dfn[x] == low[x]){ cntSCC++; do{ int t = s[headS]; in[t] = cntSCC; ins[t] = ; if(ind[t]){ len[][cntSCC] = min(len[][cntSCC] , ind[t]); len[][cntSCC] = max(len[][cntSCC] , ind[t]); } }while(s[headS--] != x); } } void create(){ ; i <= N ; i++) for(int j = head[i] ; j ; j = Ed[j].upEd) if(in[Ed[j].end] != in[i]) addEd(newEd , newHead , cntNewEd , in[i] , in[Ed[j].end]); } void dfs(int x){ if(vis[x]) return; vis[x] = ; for(int i = newHead[x] ; i ; i = newEd[i].upEd){ dfs(newEd[i].end); len[][x] = min(len[][x] , len[][newEd[i].end]); len[][x] = max(len[][x] , len[][newEd[i].end]); } } bool operator <(node a , node b){ return a.y > b.y; } int main(){ #ifdef LG freopen("4700.in" , "r" , stdin); freopen("4700.out" , "w" , stdout); #endif memset(len[] , ])); N = read(); M = read(); A = read(); B = read(); ; i <= N ; i++){ int x = read() , y = read(); if(x == A) ine[i] = ; else if(!x){ now[++cntNode].y = y; now[cntNode].ind = i; } } ; i <= M ; i++){ int a = read() , b = read() , c = read(); addEd(Ed , head , cntEd , b , a); ) addEd(Ed , head , cntEd , a , b); } sort(now + , now + cntNode + ); ; i <= cntNode ; i++) ind[now[i].ind] = i; ; i <= N ; i++) if(!vis[i]) tarjan(i); memset(vis , , sizeof(vis)); create(); ; i <= N ; i++) if(ine[i]){ dfs(in[i]); ][][in[i]]){ num[len[][in[i]]]++; num[len[][]--; } } ; i <= cntNode ; i++) num[i] += num[i - ]; ; i <= cntNode ; i++) cout << (!vis[ : num[i]) << endl; ; }
最新文章
- ListMultimap 容器
- 【转】JSP使用上传文件,并生产高清缩略图示例
- 如何用css3实现风车效果
- 13个Cat命令管理(显示,排序,建立)文件实例
- lsb_release 提示命令不存在
- 无线网络wifi (WPA/WPA2)密码破解方法
- 在腾讯云上把Laravel整合万向优图图片管理能力,打造高效图片处理服务
- 重定向URL
- window.parent.document jquery
- Hibernate注解配置与XML配置区别
- spring配置文件中context:property-placeholder导入多个独立的配置文件
- centos7查看网卡UUID
- 【CQOI2011】放棋子
- (1)Python3笔记 数据类型之Number与String
- _itemmod_gem_limit
- ubuntu安装jre
- 03_Java基础语法_第3天(Scanner、Random、流程控制语句)_讲义
- Spring 之注解事务 @Transactional(转载)
- Android学习问题记录之java.lang.UnsatisfiedLinkError
- [转] Linux 中提高 VsFTP 服务器的安全性
热门文章
- Ajax的实现及使用-原生对象
- Jni 线程JNIEnv,JavaVM,JNI_OnLoad(GetEnv返回NULL?FindClass返回NULL?)
- Java并发编程(十三)线程间协作的两种方式:wait、notify、notifyAll和Condition
- (网页)angular中实现li或者某个元素点击变色的两种方法(转)
- (网页)readonly和disabled的区别(转)
- LeetCode题解之Binary Tree Paths
- flask框架的教程--程序的基本结构[二]
- nginx、tomcat调优方向及压测网站步骤
- 使用CefSharp的一些需要注意的点
- pb数据窗口之间的传参