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);
}