在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙,而又非常聪明,他费尽心机谋划了这次盗窃行动,破解重重机关后来到这座地下宫殿前。

整座宫殿呈矩阵状,由R×C间矩形宫室组成,其中有N间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室间都由坚硬的实体墙阻隔,由一间宫室到达另一间只能通过所驼门王独创的移动方式——传送门。所驼门王为这N间藏宝宫室每间都架设了一扇传送门,没有宝藏的宫室不设传送门,所有的宫室传送门分为三种:

  1. “横天门”:由该门可以传送到同行的任一宫室;
  2. “纵寰门”:由该门可以传送到同列的任一宫室;
  3. “自由门”:由该门可以传送到以该门所在宫室为中心周围8格中任一宫室(如果目标宫室存在的话)。

深谋远虑的Henry当然事先就搞到了所驼门王当年的宫殿招标册,书册上详细记录了每扇传送门所属宫室及类型。而且,虽然宫殿内外相隔,但他自行准备了一种便携式传送门,可将自己传送到殿内任意一间宫室开始寻宝,并在任意一间宫室结束后传送出宫。整座宫殿只许进出一次,且便携门无法进行宫室之间的传送。不过好在宫室内传送门的使用没有次数限制,每间宫室也可以多次出入。

现在Henry已经打开了便携门,即将选择一间宫室进入。为得到尽多宝藏,他希望安排一条路线,使走过的不同藏宝宫室尽可能多。请你告诉Henry这条路线最多行经不同藏宝宫室的数目。

 

[无耻地借用洛谷的图片]

首先缩一下点……

然后跑DP……

很简单QAQ

在BZOJ写了7000B,成功拿到『最近几页的最长代码』成就

在洛谷跑了400ms,超级快。//好像空间还用的很少

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<iterator>
#include<utility>
#include<cmath>
#include<queue>
using namespace std;

//graph
struct no
{
	int x,y,type,code;
}nodes[100010]={0},nodes1[100010]={0},nodes2[100010]={0};
int nodenum,r,c;
int vdir1[100010]={0},vdir2[100010]={0};
//tarjan
int tstamp=0,dfn[100010]={0},low[100010]={0},stackx[100010]={0},headx=0;
int sccnum=0,belong[100010]={0};
bool instack[100010]={0};
//DAG
struct ed
{
	int pre,to;
}edge[5000010]={0};
int nodev[100010]={0},edgenum=0,pointer[100010]={0},fx,tx;
//dp
int f[100010]={0};

bool cmp1(no a,no b)
{
	if (a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
bool cmp2(no a,no b)
{
	if (a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}

void tarjan(int u)
{
	dfn[u]=low[u]=++tstamp;
	instack[u]=true;
	stackx[++headx]=u;
	int v;
	if (nodes[u].type==1)//the first condition 
	{
		int pos=vdir1[nodes[u].code];//该点在nodes1里的位置 
		for (int i=1;pos+i<=nodenum;i++)
		{
			if (nodes1[pos+i].x==nodes[u].x)
			{
				v=nodes1[pos+i].code;
				if (!dfn[v])
				{
					tarjan(v);
					low[u]=min(low[u],low[v]);
				}
				else if (instack[v]) low[u]=min(low[u],dfn[v]);
			}
			else break;
		}
		for (int i=1;pos-i>=1;i++)
		{
			if (nodes1[pos-i].x==nodes[u].x)
			{
				v=nodes1[pos-i].code;
				if (!dfn[v])
				{
					tarjan(v);
					low[u]=min(low[u],low[v]);
				}
				else if (instack[v]) low[u]=min(low[u],dfn[v]);
			}
			else break;
		}
	}
	else if (nodes[u].type==2)//the second condition 
	{
		int pos=vdir2[nodes[u].code];
		for (int i=1;pos+i<=nodenum;i++)
		{
			if (nodes2[pos+i].y==nodes[u].y)
			{
				v=nodes2[pos+i].code;
				if (!dfn[v])
				{
					tarjan(v);
					low[u]=min(low[u],low[v]);
				}
				else if (instack[v]) low[u]=min(low[u],dfn[v]);
			}
			else break;
		}
		for (int i=1;pos-i>=1;i++)
		{
			if (nodes2[pos-i].y==nodes[u].y)
			{
				v=nodes2[pos-i].code;
				if (!dfn[v])
				{
					tarjan(v);
					low[u]=min(low[u],low[v]);
				}
				else if (instack[v]) low[u]=min(low[u],dfn[v]);
			}
			else break;
		}
	}
	else//the third condition 
	{
		int pos=vdir1[nodes[u].code];
		for (int i=1;pos+i<=nodenum;i++)
		{
			int nx=nodes1[pos+i].x,ny=nodes1[pos+i].y,posy=nodes[u].y,posx=nodes[u].x;//get position
			if ((nx-posx<=1) && (abs(ny-posy)<=1))
			{
				v=nodes1[pos+i].code;
				if (!dfn[v])
				{
					tarjan(v);
					low[u]=min(low[u],low[v]);
				}
				else if (instack[v]) low[u]=min(low[u],dfn[v]);
			}
			else if (nx>posx+1) break;
		}
		for (int i=1;pos-i>=1;i++)
		{
			int nx=nodes1[pos-i].x,ny=nodes1[pos-i].y,posy=nodes[u].y,posx=nodes[u].x;//get position
			if ((posx-nx<=1) && (abs(ny-posy)<=1))
			{
				v=nodes1[pos-i].code;
				if (!dfn[v])
				{
					tarjan(v);
					low[u]=min(low[u],low[v]);
				}
				else if (instack[v]) low[u]=min(low[u],dfn[v]);
			}
			else if (nx<posx-1) break;
		}
	}
	
	if (low[u]==dfn[u])//still instack
	{
		int cache1; sccnum++;
		do
		{
			cache1=stackx[headx];
			headx--;
			belong[cache1]=sccnum;
			instack[cache1]=false;
		}while (cache1!=u);
	}
}

inline void Insert()
{
	edgenum++;
	edge[edgenum].pre=pointer[fx];
	edge[edgenum].to=tx;
	pointer[fx]=edgenum;
}

inline void Shrink()
{
	for (register int k=1;k<=nodenum;k++)
	{
		fx=belong[k];
		nodev[fx]++;
		switch (nodes[k].type)
		{
			case 1:
				{
				int pos=vdir1[nodes[k].code];
				for (int i=1;pos+i<=nodenum;i++)
				{
					if (nodes1[pos+i].x==nodes[k].x)
					{
						if (fx!=belong[nodes1[pos+i].code])
						{
							tx=belong[nodes1[pos+i].code];
							Insert();
						}
					}
					else break;
				}
				for (int i=1;pos-i>=1;i++)
				{
					if (nodes1[pos-i].x==nodes[k].x)
					{
						if (fx!=belong[nodes1[pos-i].code])
						{
							tx=belong[nodes1[pos-i].code];
							Insert();
						}
					}
					else break;
				}
				}
				break;
			case 2:
				{
				int pos=vdir2[nodes[k].code];
				for (int i=1;pos+i<=nodenum;i++)
				{
					if (nodes2[pos+i].y==nodes[k].y)
					{
						if (fx!=belong[nodes2[pos+i].code])
						{
							tx=belong[nodes2[pos+i].code];
							Insert();
						}
					}
					else break;
				}
				for (int i=1;pos-i>=1;i++)
				{
					if (nodes2[pos-i].y==nodes[k].y)
					{
						if (fx!=belong[nodes2[pos-i].code])
						{
							tx=belong[nodes2[pos-i].code];
							Insert();
						}
					}
					else break;
				}
				}
				break;
			case 3:
				{
				int pos=vdir1[nodes[k].code];
				for (int i=1;pos+i<=nodenum;i++)
				{
					int nx=nodes1[pos+i].x,ny=nodes1[pos+i].y,posy=nodes[k].y,posx=nodes[k].x;//get position
					if ((nx-posx<=1) && (abs(ny-posy)<=1))
					{
						if (fx!=belong[nodes1[pos+i].code])
						{
							tx=belong[nodes1[pos+i].code];
							Insert();
						}
					}
					else if (nx>posx+1) break;
				}
				for (int i=1;pos-i>=1;i++)
				{
					int nx=nodes1[pos-i].x,ny=nodes1[pos-i].y,posy=nodes[k].y,posx=nodes[k].x;//get position
					if ((posx-nx<=1) && (abs(ny-posy)<=1))
					{
						if (fx!=belong[nodes1[pos-i].code])
						{
							tx=belong[nodes1[pos-i].code];
							Insert();
						}
					}
					else if (nx<posx-1) break;
				}
				}
				break;
		}
	}
}

int dp(int nownode)
{
	if (!f[nownode])
	{
		int prex=pointer[nownode];
		while (prex)
		{
			if (!f[edge[prex].to]) f[nownode]=max(f[nownode],dp(edge[prex].to));
			else f[nownode]=max(f[nownode],f[edge[prex].to]);
			prex=edge[prex].pre;
		}
		f[nownode]+=nodev[nownode];
	}
	return f[nownode];
}

int main()
{
	scanf("%d%d%d",&nodenum,&r,&c);
	for (int i=1;i<=nodenum;i++) 
	{
		scanf("%d%d%d",&nodes[i].x,&nodes[i].y,&nodes[i].type);
		nodes[i].code=i;
	}
	memcpy(nodes1,nodes,sizeof(nodes));
	memcpy(nodes2,nodes,sizeof(nodes));
	sort(nodes1+1,nodes1+nodenum+1,cmp1);
	sort(nodes2+1,nodes2+nodenum+1,cmp2);
	for (int i=1;i<=nodenum;i++)//编号为i的点在nodes1和nodes2数组里的位置 
	{
		vdir1[nodes1[i].code]=i;
		vdir2[nodes2[i].code]=i;
	}
	
	for (int i=1;i<=nodenum;i++) if (!belong[i]) tarjan(i);
	Shrink();
	
	int ans=0;
	for (int i=1;i<=sccnum;i++)
	{
		if (!f[i]) dp(i);
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注