起初从boat大牛那里听说了这题，挺有意思的，就做了做。

题意：一辆坦克从N*M矩阵的左上角出发，每次往右或往 下走一格，每格可以是'#'(表示不可以走),'*'表示传送门，或者是数字，表示在该格可以获得的值（只能取一次），传送门可以传送到指定位置，你可以选择被传送或者走相邻的格，问坦克可以获得的值的和最大为多少。

解析：第一次看应该是个DP，（如果无传送门且可以走K轮，可以用网络流），但是矩阵中有传送门的存在，有可能形成环，所以要转化成DAG（有向无环图），可以以格子的相邻关系建边，然后求SCC，缩点再构图，边权为指向的格子的值，后求最长路（可以搜索，可以DP）。

WA了好几次，传送门有可能传到'#'的格子，格子是'#'的时候也要向相邻格子建边，题目求的是坦克可以获得的最大值，而不是到右下角的值（上回做了道类似的网络流，惯性导致想当然了）。

最后贴个代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

struct Edge
{
	int v;
	int next;
}buf[50000];

int head[2000],head2[2000],nE;
bool instack[2200];
int dfn[2020],low[2020],idx,Bcnt;
int stack[2020],top;
int Belong[2020];
int ores[2200];
int Bores[2200];
int N,M;

void addEdge(int u,int v)
{
	buf[nE].v=v;buf[nE].next=head[u];head[u]=nE++;
}

void addEdge2(int u,int v)
{
	buf[nE].v=v;buf[nE].next=head2[u];head2[u]=nE++;
}


void Tarjan(int cur)
{
	dfn[cur]=low[cur]=++idx;
	stack[top++]=cur;
	instack[cur]=true;

	for(int i=head[cur];i!=-1;i=buf[i].next)
	{
		int v=buf[i].v;
		if(!dfn[v])
		{
			Tarjan(v);
			if(low[cur]>low[v])
				low[cur]=low[v];
		}
		else if(instack[v]&&low[cur]>dfn[v])
		{
			low[cur]=dfn[v];
		}
	}
	if(dfn[cur]==low[cur])
	{
		Bcnt++;
		Bores[Bcnt]=0;
		int j;
		do
		{
			j=stack[--top];
			instack[j]=false;
			Belong[j]=Bcnt;
			Bores[Bcnt]+=ores[j];
		}while(j!=cur);
	}
}

void Rebuld()
{
	memset(head2,0xff,sizeof(head2));
	for(int i=0;i<N*M;i++)
		for(int j=head[i];j!=-1;j=buf[j].next)
		{
			int v=buf[j].v;
			if(Belong[i]!=Belong[v])
				addEdge2(Belong[i],Belong[v]);
		}
}

void go()
{
	memset(dfn,0,sizeof(dfn));
	memset(instack,false,sizeof(instack));
	idx=Bcnt=top=0;
	for(int i=0;i<N*M;i++)
		if(!dfn[i])
			Tarjan(i);
	Rebuld();
	int dis[2020];
	memset(dis,0,sizeof(dis));
	dis[Belong[0]]=Bores[Belong[0]];
	queue<int> que;
	que.push(Belong[0]);
	bool inq[2020];
	memset(inq,false,sizeof(inq));
	inq[Belong[0]]=true;
	while(!que.empty())
	{
		int cur=que.front();que.pop();
		inq[cur]=false;
		for(int i=head2[cur];i!=-1;i=buf[i].next)
		{
			int v=buf[i].v;
			if(dis[v]<dis[cur]+Bores[v])
			{
				dis[v]=dis[cur]+Bores[v];
				if(!inq[v])
				{
					inq[v]=true;
					que.push(v);
				}
			}
		}
	}
	int ans=-1;
	for(int i=1;i<=Bcnt;i++)
	   if(dis[i]>ans)
	       ans=dis[i];
	printf("%d\n",ans);
}

char map[45][45];

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		memset(head,0xff,sizeof(head));
		nE=0;
		scanf("%d%d",&N,&M);
		for(int i=0;i<N;i++)
			scanf("%s",map[i]);
		memset(ores,0,sizeof(ores));
		for(int i=0,r,c;i<N;i++)
			for(int j=0;j<M;j++)
				if(map[i][j]!='#')
				{	
					if(i+1<N&&map[i+1][j]!='#')addEdge(i*M+j,(i+1)*M+j);
					if(j+1<M&&map[i][j+1]!='#')addEdge(i*M+j,i*M+j+1);
					ores[i*M+j]=map[i][j]-'0';
					if(map[i][j]=='*')
				    {
                       ores[i*M+j]=0;
                       scanf("%d%d",&r,&c);
                       if(map[r][c]!='#')
                            addEdge(i*M+j,r*M+c);
				    }
				}
		go();
	}
	return 0;
}

0MS

• 相关文章