Blackops

初心易得，始终难守

0%

POJ 3311 Hie with the Pie（floyed预处理+状压+优先队列分支限界法求哈密顿回路）

发表于 分类于 ， 阅读次数： 30

Hie with the Pie
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 8401 Accepted: 4582

Description

The Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can afford to hire only one driver to do the deliveries. He will wait for 1 or more (up to 10) orders to be processed before he starts any deliveries. Needless to say, he would like to take the shortest route in delivering these goodies and returning to the pizzeria, even if it means passing the same location(s) or the pizzeria more than once on the way. He has commissioned you to write a program to help him.

Input

Input will consist of multiple test cases. The first line will contain a single integer n indicating the number of orders to deliver, where 1 ≤ n ≤ 10. After this will be n + 1 lines each containing n + 1 integers indicating the times to travel between the pizzeria (numbered 0) and the n locations (numbers 1 to n). The jth value on the ith line indicates the time to go directly from location i to location j without visiting any other locations along the way. Note that there may be quicker ways to go from i to j via other locations, due to different speed limits, traffic lights, etc. Also, the time values may not be symmetric, i.e., the time to go directly from location i to j may not be the same as the time to go directly from location j to i. An input value of n = 0 will terminate input.

Output

For each test case, you should output a single number indicating the minimum time to deliver all of the pizzas and return to the pizzeria.

Sample Input

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0
Sample Output

8

题目链接：POJ 3311
最近算法课有一个作业要用优先队列来优化分支限界法求哈密顿回路即TSP问题，要画出优先队列的解空间树，不知道如何实现，于是只能找道题来做做
写了好一会儿一直WA，后来发现是状态不对，应该多加一维表示最后所在点才行。
分支限界法根据书上定义应该是把不必要的状态剪枝去掉，在代码中体现在不压入优先队列，那如何剪枝呢，假设我们要拓展的下一个状态是nxt，如果nxt已经被计算过且其代价大于当前的估算代价上界，那么显然nxt就没必要存在，扔掉即可。
代码上实现的话就是用二进制[1,2n)表示当前走过的点状态，Mincost[st][u记录是当前走过的点的状态st，此状态最后所在点为u的最小代价，那么可以得到状态转移方程:

dp[st|(1<<v)][v]=min(dp[st|(1<<v)][v],dp[st][u]+cost(u,v)),st&(1<<v)=0

如果0−n都走过之后再回到0可以特判一下让此时的第0个位置作为第n+1的位置处理。
要输出解空间树的话就给每一个状态加上标号，每次压入队列时输出当前节点的标号和状态，下一个节点的标号的状态。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 12;
struct edge
{
    int to, nxt, w;
    edge() {}
    edge(int _to, int _nxt, int _w): to(_to), nxt(_nxt), w(_w) {}
} E[N * N];
int head[N], tot;
int dis[(1 << N) + 10][N], n;
int G[N][N];

void init()
{
    CLR(head, -1);
    tot = 0;
    CLR(dis, INF);
    CLR(G, INF);
}
inline void add(int s, int t, int w)
{
    E[tot] = edge(t, head[s], w);
    head[s] = tot++;
}
struct info
{
    int u, st, cost;
    bool operator<(const info &rhs)const
    {
        return cost > rhs.cost;
    }
};
void bfs()
{
    priority_queue<info>Q;
    CLR(dis, INF);
    Q.push((info) {0, 1 << 0, 0});
    dis[Q.top().st][Q.top().u] = 0;
    while (!Q.empty())
    {
        info u = Q.top();
        Q.pop();
        for (int i = head[u.u]; ~i; i = E[i].nxt)
        {
            int v = E[i].to;
            int w = E[i].w;
            if (u.st == ((1 << (n + 1)) - 1))
            {
                if (v == 0 && dis[u.st][u.u] + w < dis[(1 << (n + 2)) - 1][0])
                {
                    dis[(1 << (n + 2)) - 1][0] = dis[u.st][u.u] + w;
                    Q.push((info) {0, (1 << (n + 2)) - 1, dis[(1 << (n + 2)) - 1][0]});
                }
            }
            else
            {
                if ((!(u.st & (1 << v))) && dis[u.st][u.u] + w < dis[u.st | (1 << v)][v])
                {
                    dis[u.st | (1 << v)][v] = dis[u.st][u.u] + w;
                    Q.push((info) {v, u.st | (1 << v), dis[u.st | (1 << v)][v]});
                }
            }
        }
    }
}
int main(void)
{
    int i, j, k;
    while (~scanf("%d", &n) && n)
    {
        init();
        for (i = 0; i <= n; ++i)
            for (j = 0; j <= n; ++j)
                scanf("%d", &G[i][j]);
        for (k = 0; k <= n; ++k)
            for (i = 0; i <= n; ++i)
                for (j = 0; j <= n; ++j)
                    G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
        for (i = 0; i <= n; ++i)
        {
            for (j = 0; j <= n; ++j)
            {
                if (i == j)
                    continue;
                add(i, j, G[i][j]);
            }
        }
        bfs();
        printf("%d\n", dis[(1 << (n + 2)) - 1][0]);
    }
    return 0;
}