自动搬运

查看原文

来自洛谷，原作者为

	caddy **

搬运于2025-08-24 21:38:46，当前版本为作者最后更新于2018-02-06 20:45:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻的构思 一开始想到深度优先搜索 以每个资源点为状态，包括起点。 建一个图，值得注意的是假如点a与点b之间有一个点，那么不连边。 否则就连边,表示可以做决策从a去b。 具体思路就是，如果a,b有点c那么肯定顺道去c了。所以a不会直接到b.之后从起点dfs整个图即可，记录最大答案.

#include<cstdio>
#define max(x,y) ((x)>(y))?(x):(y)
#define min(x,y) ((x)<(y))?(x):(y)
int abs(int x)
{
	return (x>0)?x:-x;
}
struct word
{
	int x,y,v;
};
word node[205];
int n,m,t,ans,g[205][205],vic[205];
bool check(int a,int b)
{
	int lx=max(node[a].x,node[b].x) ,
	ly=max(node[a].y,node[b].y),
	rx=min(node[a].x,node[b].x),
	ry=min(node[a].y,node[b].y);
	for(int i=0;i<=m;i++)
	if(i!=a&&i!=b)
	if(node[i].x>=rx&&node[i].x<=lx)
	if(node[i].y>=ry&&node[i].y<=ly)
	return false;
	return true;
}
void  dfs(int x,int use_t,int score)
{
	ans=max(score,ans);
	for(int i=0;i<=m;i++)
	if(g[x][i]&&use_t+g[x][i]<=t&&(!vic[i]))
	vic[i]=1,dfs(i,use_t+g[x][i],score+node[i].v),vic[i]=0;
}
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=m;i++)
	scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].v);	
	for(int i=0;i<=m;i++)
	for(int j=0;j<=m;j++)
	{
		if(i!=j&&check(i,j))
		g[i][j]=abs(node[j].y-node[i].y)+
		abs(node[j].x-node[i].x);
	}
	for(int i=0;i<=m;i++,printf("\n"))
	for(int j=0;j<=m;j++)
	printf("%d ",g[i][j]);
	dfs(0,0,0);
	printf("%d",ans);
}