记住:map一定要这么用:

if(mp[x[i]+dx[j]].find(y[i]+dy[j])!=mp[x[i]+dx[j]].end()) add(i,mp[x[i]+dx[j]][y[i]+dy[j]]);

  而不是

R tmp=mp[x[i]+dx[j]][y[i]+dy[j]];
if(tmp) add(i,tmp);

别问我为什么QAQ

建图:选定一个横天门,向在这一行上的横天门连无向边,剩下的门连有向边;纵寰门一样的方法

用map判 自由_门 旁边八个点是否存在,存在就连边;

最后tarjan缩点,用dp求最长路

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#define R register int
const int dx[]={,,,,,-,-,-},dy[]={,,,-,-,-,,};
using namespace std;
inline int g() {
R ret=; register char ch; while(!isdigit(ch=getchar())) ;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret;
}
#define pb(x) push_back(x)
int k,n,m,cnt=,ind,cc,top,ans,num;
int lst[],lst2[],x[],y[],op[],d[];
int vr[],nxt[],fir[],dfn[],scc[],stk[],low[],c[];
vector<int>a[],b[];
map<int,int> mp[];
bool vis[];
inline void add(int u,int v) {if(u==v) return ;vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt;}
inline void init() {
for(R i=;i<=n;++i) {
R x=,sz=a[i].size();
for(R j=;j<sz;++j) if(op[a[i][j]]==) {x=a[i][j]; break;}
for(R j=;j<sz;++j) {add(x,a[i][j]); if(op[a[i][j]]==) add(a[i][j],x);}
}
for(R i=;i<=m;++i) {
R x=,sz=b[i].size();
for(R j=;j<sz;++j) if(op[b[i][j]]==) {x=b[i][j]; break;}
for(R j=;j<sz;++j) {add(x,b[i][j]); if(op[b[i][j]]==) add(b[i][j],x);}
}
for(R i=;i<=k;++i) if(op[i]==) for(R j=;j<;++j)
if(mp[x[i]+dx[j]].find(y[i]+dy[j])!=mp[x[i]+dx[j]].end()) add(i,mp[x[i]+dx[j]][y[i]+dy[j]]);void tarjan(int u) { low[u]=dfn[u]=++num; stk[++top]=u,vis[u]=true;
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
} else if(vis[v]) low[u]=min(low[u],dfn[v]);
} if(low[u]==dfn[u]) {
R tmp; ++cc;
do tmp=stk[top],--top,vis[tmp]=false,c[tmp]=cc,++scc[cc]; while(tmp!=u);
}
}
int vv[],nn[],ff[];
inline void addc(int u,int v) {vv[++cnt]=v,nn[cnt]=ff[u],ff[u]=cnt;}
inline void solve() {
cnt=; for(R u=;u<=k;++u) for(R i=fir[u];i;i=nxt[i])
if(c[u]!=c[vr[i]]) addc(c[u],c[vr[i]]);
}
inline void dp(int u) { vis[u]=true;
for(R i=ff[u];i;i=nn[i]) { R v=vv[i];
if(!vis[v]) dp(v);
d[u]=max(d[v],d[u]);
} d[u]+=scc[u]; ans=max(d[u],ans);
}
signed main() {
k=g(),n=g(),m=g();
for(R i=;i<=k;++i) {
x[i]=g(),y[i]=g(),op[i]=g();
mp[x[i]][y[i]]=i;
a[x[i]].pb(i),b[y[i]].pb(i);
} init(); for(R i=;i<=k;++i) if(!dfn[i]) tarjan(i);
solve(); memset(vis,false,sizeof(vis));
for(R i=;i<=cc;++i) if(!vis[i]) dp(i);
printf("%d\n",ans); return ;
}

2019.04.21

upd:5秒后 (发布时显示:博文中含有违规内容: 自_由_门! (并没有下划线)    ????不知所言)

最新文章

  1. 如何定位Oracle数据库被锁阻塞会话的根源
  2. C++ 基础知识复习(六)
  3. deepin linux 安装 mysql
  4. 敏捷软件开发 Agile software Development(转)
  5. 图像分割之(二)Graph Cut(图割)
  6. android 项目学习随笔十(自定义ProgressBar)
  7. matlab norm的使用
  8. Java实现单向链表的增删改查
  9. iOS中使用图片作为颜色的背景图
  10. commit后数据库干的工作
  11. Qt Project的持续集成方案
  12. Teclast/台电 P98HD四核测评9.7寸台电P98HD 评测体验 (转载)
  13. Word 文字转表格
  14. 记VUE的v-on:textInput无法执行事件的BUG
  15. &lt;pre&gt;标签的基本样式设置
  16. MP实战系列(六)之代码生成器讲解
  17. 微软笔记工具OneNote
  18. Java类的继承与多态特性-入门笔记
  19. 【转】.NET Framework、C#语言、IDE、CLR 版本历史及其差异
  20. font-size对展示的影响

热门文章

  1. ACM学习历程—HDU5490 Simple Matrix (数学 &amp;&amp; 逆元 &amp;&amp; 快速幂) (2015合肥网赛07)
  2. ACM学习历程—HDU5407 CRB and Candies(数论)
  3. 【LeetCode】015 3Sum
  4. 洛谷【P3407】散步
  5. TFS自定义开发中的反射应用
  6. HDOJ1242(延时迷宫BFS+优先队列)
  7. HDOJ1114(完全背包)
  8. mysql: not unique table/alias error. 如何解决
  9. web攻击之六:DNS攻击原理与防范
  10. 如何在Windows平台使用VS搭建C++/Lua的开发环境