bzoj2825:[AHOI2012]收集资源

传送门

看到数据范围这么小，就没想过暴力的办法么

考虑肯定是从近走到远，所以走的点之间一定没有其他的点，所以我们就可以暴力的建图，然后暴力的去dfs就好了

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

void read(int &x) {

    char ch; bool ok;

    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;

    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;

}

void print(int x){

    if(x<0)putchar('-'),x=-x;

    if(x>9)print(x/10);

    putchar(x%10+'0');

}

#define rg register

const int maxn=210;

int n,m,T,ans,d[maxn][maxn];bool vis[maxn];

struct oo{int x,y,v;}a[maxn];

void dfs(int x,int now,int val)

{

	if(now<=T)ans=max(ans,val);

	else return ;

	for(rg int i=1;i<=m;i++)

		if(d[x][i]&&!vis[i])

			vis[i]=1,dfs(i,now+d[x][i],val+a[i].v),vis[i]=0;

}

int main()

{

	read(n),read(m),read(T);

	for(rg int i=1;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].v);

	for(rg int i=0;i<=m;i++)

		for(rg int j=0;j<=m;j++)

			if(i!=j)

			{

				bool flag=0;

				for(rg int k=1;k<=m;k++)

					if(k!=i&&k!=j)

					{

						int lx=min(a[i].x,a[j].x),rx=max(a[i].x,a[j].x),ly=min(a[i].y,a[j].y),ry=max(a[i].y,a[j].y);

						if(a[k].x>=lx&&a[k].x<=rx&&a[k].y>=ly&&a[k].y<=ry){flag=1;break;}

					}

				if(!flag)d[i][j]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);

			}

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

}

巴特西

bzoj2825:[AHOI2012]收集资源

传送门

最新文章

热门文章