hdu 4568 Hunter bfs建图+TSP状压DP

想AC的人请跳过这一段。。。

题目应该都能读懂。但是个人觉得这题出的很烂，意思太模糊了。

首先，进出次数只能是一次！！这个居然在题目中没有明确说明，让我在当时看到题目的时候无从下手。

因为我想到了这几个数据：

1 1 1 1 9 1 -1 -1 -1

-1-1-1 9 9 9 -1 1 -1

1 1 1 1 9 1 -1 -1 -1

6个宝藏 四个角是宝藏 中间是宝藏

第一个数据如果进出2次，就可以拿走全部的6个宝藏，也符合题目的“bring out all treasures he can take”。

即使是规定了进出只能一次，那这个数据又该输出什么？（ if nothing James can get, please output 0）

第二个数据如果进出4次，就可以最快的拿走全部宝藏。

第三个数据唯一的宝藏拿不走。

不过，这题的测试数据中并没有上面的例子。

以上为个人YY

以下为题解：

进出一次，找到所有能找到的宝藏，裸的TSP问题。

首先选一个自己喜欢的算法建图。将整个边界理解成一个点，找到每两个宝藏之间的最短距离和每个宝藏的离边界点的最短距离。

然后就是TSP，状态压缩DP解。

#include
#include
#include
#include
#include
using namespace std;
int n,m,tre;
int ID[205][205];
int map[205][205];
int dis[20][20];
bool vis[205][205];
int dp[1<<16][20];
struct node
{
    int x,y;
}t[20];
struct node2
{
    int x,y,dis;
    bool operator <(const node2 & f) const
    {
        return dis>f.dis;
    }
};
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
bool isok(int x,int y)
{
    return x>=0&&x=0&&y Q;
    int v[20]={0};
    memset(vis,0,sizeof(vis));
    node2 f,r;
    r.x=t[k].x;
    r.y=t[k].y;
    r.dis=0;
    Q.push(r);
    v[k]=1;
    vis[r.x][r.y]=1;
    int tot=1,id;
    while(!Q.empty())
    {
        f=Q.top(); Q.pop();
        if(!v[0]&&(f.x==0||f.y==0||f.x==n-1||f.y==m-1))
        {
            v[0]=1;
            dis[k][0]=f.dis;
            dis[0][k]=f.dis+map[t[k].x][t[k].y];
            tot++;
            if(tot==tre+1) return;
        }
        id=ID[f.x][f.y];
        if(id&&!v[id])
        {
            tot++;
            v[id]=1;
            dis[k][id]=f.dis;
            if(tot==tre+1) return;
        }
        for(int d=0;d<4;d++)
        {
            r.x=f.x+dx[d];
            r.y=f.y+dy[d];
            r.dis=f.dis+map[r.x][r.y];
            if(isok(r.x,r.y)&&!vis[r.x][r.y])
            {
                vis[r.x][r.y]=1;
                Q.push(r);
            }
        }
    }
}
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        memset(ID,0,sizeof(ID));
        memset(dis,0x3f,sizeof(dis));
        memset(dp,0x3f,sizeof(dp));
        scanf("%d%d",&n,&m);
        for(int i=0;i>j)&1)
                {
                    for(int k=0;k<=tre;k++)
                    {
                        if((i>>k)&1)
                        {
                            dp[i][j]=min(dp[i][j],dp[i&(~(1<