【题解】SDOI2010所驼门王的宝藏(强连通分量+优化建图)

最开始我想写线段树优化建图的说，数据结构学傻了233

虽然矩阵很大，但是没什么用，真正有用的是那些关键点

考虑关键点的类型：

横走型
竖走型
八连通型

本质上只有两种类型(走一大串/走八连通)，我们考虑这样一种建图方法：

对于每一行每一列建立一个点(点权为\(0\))
对于关键点建立一个点(点权为\(1\))

然后考虑这样一种建图方式，得到一个有点权无边权图

关键点所在的行与列无偿地向这个关键点连边
横走型的关键点向行连一条边，竖走型同理
八连通型直接向周围的关键点连边

题目要求走到的点最多，也就是求一条最长路径，但是显然这个图上可能有正环，但是点权贡献只能算一次，自然想到直接缩点。缩完点后得到一个\(DAG\)，直接在这个\(DAG\)上\(dp\)

\(dp_i\)表示从这个节点出发最长的路径，直接转移。

分析点数，显然是\(O(3n)\)，分析边数，一个点最多连接十条边，\(tarjin\)是\(O(n)\)的，但是我们用了\(map\)所以复杂度\(O(n\log n)\)，实际上，直接用unordered_map就是\(O(n)\)了，就帅一点...

至于实现，直接用\(map\)存std::pair < int ,int >就好了

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=1e5+5;

struct E{

      int to,nx;

      E(){to=nx=0;}

      E(const int&a,const int&b){to=a;nx=b;}

};

vector < E > e,e2;

pair < int ,int > node[maxn];

int head[maxn*3];

int head2[maxn*3];

int TT[maxn];

int dp[maxn*3];

int n,m,k;

void add2(const int&fr,const int&to){

      e2.push_back(E(to,head2[fr]));

      head2[fr]=e2.size()-1;

}

void add(const int&fr,const int&to){

      e.push_back(E(to,head[fr]));

      head[fr]=e.size()-1;

}

int idx[maxn],idy[maxn];

int w[maxn*3];

int stk[maxn*3];

int qaq,top;

int be[maxn*3];

int siz[maxn*3];

int dfn[maxn*3],low[maxn*3],in[maxn*3];

int tim,ans;

int qaqcnt;

int dfs2(const int&now){

      if(dp[now]) return dp[now];

      register int ret=0;

      for(register int t=head2[now];t;t=e2[t].nx)

	    ret=max(ret,dfs2(e2[t].to));

      return dp[now]=ret+siz[now];

}

void dfs(const int&now){

      dfn[now]=low[now]=++tim;in[now]=1;stk[++top]=now;

      for(register int t=head[now];t;t=e[t].nx){

	    if(!dfn[e[t].to])

		  dfs(e[t].to),low[now]=min(low[now],low[e[t].to]);

	    if(dfn[e[t].to]&&in[e[t].to])

		  low[now]=min(low[now],dfn[e[t].to]);

      }

      if(dfn[now]==low[now]){

	    register int temp=0;

	    ++qaq;

	    do{

		  temp=stk[top--];

		  in[temp]=0;siz[qaq]+=w[temp];

		  be[temp]=qaq;

	    }while(temp!=now);

      }

}

map < pair < int ,int > , int > s;

inline int init(const int&a,const int&b,const int&c){

      e.push_back(E());  e.push_back(E());

      e2.push_back(E()); e2.push_back(E());

      qaqcnt=k=a;n=b;m=c;

      for(register int t=1;t<=k;++t){

	    register int t1=qr(),t2=qr(),t3=qr();

	    node[t].first=t1;

	    node[t].second=t2;

	    TT[t]=t3; w[t]=1;

	    s[make_pair(t1,t2)]=t;

	    if(!idx[t1]) idx[t1]=++qaqcnt;

	    if(!idy[t2]) idy[t2]=++qaqcnt;

	    add(idx[t1],t);

	    add(idy[t2],t);

      }

      for(register int t=1;t<=k;++t){

	    if(TT[t]==1) add(t,idx[node[t].first]);

	    if(TT[t]==2) add(t,idy[node[t].second]);

	    if(TT[t]==3)

		  for(register int dx=-1;dx<=1;++dx)

			for(register int dy=-1;dy<=1;++dy)

			      if(dx||dy){

				    auto f=s.find(make_pair(node[t].first+dx,node[t].second+dy));

				    if(f!=s.end()) add(t,f->second);

			      }

      }

      for(register int t=1;t<=qaqcnt;++t)

	    if(!dfn[t]) dfs(t);

      for(register int t=1;t<=qaqcnt;++t)

	    for(register int i=head[t];i;i=e[i].nx)

		  if(be[e[i].to]!=be[t])

			add2(be[t],be[e[i].to]);

      for(register int t=1;t<=qaq;++t)

	    ans=max(ans,dfs2(t));

      printf("%d\n",ans);

      return 0;

}

int main(){

      int a=qr(),b=qr(),c=qr();

      return init(a,b,c);

}

巴特西

【题解】SDOI2010所驼门王的宝藏(强连通分量+优化建图)

【题解】SDOI2010所驼门王的宝藏(强连通分量+优化建图)

最新文章

热门文章