题解 P2535 【[AHOI2012]收集资源】

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