BZOJ1515 : [POI2006]Lis-The Postman
postman The LIS
2023-09-11 14:15:04 时间
首先,如果这个图本身就不存在欧拉回路,那么显然无解。
对于每个子串:
1.如果里面有不存在的边,那么显然无解。
2.如果里面有一条边重复出现,那么显然也无解。
3.对于每条边,维护其前驱与后继,若前驱或后继超过$1$个,那么显然也无解。
如此所有边将形成一条条链或者环的结构,如果存在环,那么显然也无解。
对于每条链,在新图中添加链头到链尾的边,然后判断新图中是否存在从$1$开始的欧拉回路即可。
时间复杂度$O(m\log m)$。
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; const int N=50010,M=200010; int n,m,q,i,j,k,pos,cnt,d[N],a[M],b[M],last[M],pre[M],nxt[M]; int g[N],V[M],W[M],NXT[M],vis[M],ed; struct E{int x,y;}e[M]; inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} inline bool cmp(const E&a,const E&b){return a.x==b.x?a.y<b.y:a.x<b.x;} void NIE(){puts("NIE");exit(0);} inline int ask(int x,int y){ int l=1,r=m,mid; while(l<=r){ mid=(l+r)>>1; if(e[mid].x==x&&e[mid].y==y)return mid; if(e[mid].x<x||e[mid].x==x&&e[mid].y<y)l=mid+1;else r=mid-1; } return 0; } inline void add(int x,int y,int z){d[x]++,d[y]--;V[++ed]=y;W[ed]=z;NXT[ed]=g[x];g[x]=ed;} void dfs(int x){ for(int&i=g[x];i;){ if(vis[i]){i=NXT[i];continue;} vis[i]=1; dfs(V[i]); } } int main(){ read(n),read(m); for(i=1;i<=m;i++)read(e[i].x),read(e[i].y),d[e[i].x]++,d[e[i].y]--; for(i=1;i<=n;i++)if(d[i])NIE(); sort(e+1,e+m+1,cmp); read(q); for(pos=1;pos<=q;pos++){ read(k); for(i=1;i<=k;i++)read(a[i]); for(i=1;i<k;i++){ b[i]=ask(a[i],a[i+1]); if(!b[i])NIE(); if(last[b[i]]==pos)NIE(); last[b[i]]=pos; } for(k--,i=1;i<k;i++){ if(!nxt[b[i]])nxt[b[i]]=b[i+1]; else if(nxt[b[i]]!=b[i+1])NIE(); if(!pre[b[i+1]])pre[b[i+1]]=b[i]; else if(pre[b[i+1]]!=b[i])NIE(); } } for(i=1;i<=n;i++)d[i]=0; for(i=1;i<=m;i++)if(!pre[i]){ for(k=0,j=i;j;j=nxt[j])a[++k]=j,cnt++; add(e[i].x,e[a[k]].y,a[k]); } if(cnt<m)NIE(); if(!g[1])NIE(); for(i=1;i<=n;i++)if(d[i])NIE(); dfs(1); for(i=2;i<=n;i++)if(g[i])NIE(); return puts("TAK"),0; }
相关文章
- postman 用环境变量Environment实现多服务器版本
- 安卓 android studio 报错 The specified Android SDK Build Tools version (27.0.3) is ignored, as it is below the minimum supported version (28.0.3) for Android Gradle
- Mysql 的异常:The last packet successfully received from the server was 90 milliseconds ago. The last packet sent successfully to the server was 43,603,303 milliseconds ago. is longer than the server con
- 一统江湖的大前端(3) DOClever——你的Postman有点Low
- 记录一次在生成数据库服务器上出现The timeout period elapsed prior to completion of the operation or the server is not responding.和Exception has been thrown by the target of an invocation的解决办法
- 【异常】The dependencies of some of the beans in the application context form a cycle
- postman发送json格式的post请求
- java错误:The superclass "javax.servlet.http.HttpServlet" was not found on the Java Bu
- Reporting Service 服务启动时报错The service did not respond to the start or control request in a timely fashion
- postman:用postman实现post提交json数据(postman 7.31.1)
- sharepoint2010:The number of items in this list exceeds the list view threshold, which is 20000 items.
- [Angular2 Router] Optional Route Query Parameters - The queryParams Directive and the Query Parameters Observable
- 如何使用 Postman 发送 SAP OData Batch 请求到 ABAP 后台服务器试读版
- Paper:LSTM之父眼中的深度学习十年简史《The 2010s: Our Decade of Deep Learning / Outlook on the 2020s》的解读
- EnvironmentNotWritableError: The current user does not have write permissions to the targe...
- 【问题解决】The connection to the server localhost:8080 was refused
- Postman连接数据库
- 测试新手如何用Postman做接口自动化测试
- Postman 中级使用教程,你真的会用Postman吗?
- SoapUI、Jmeter、Postman三种接口测试工具的比较分析
- postman插件下载、安装教程