本文共 3913 字，大约阅读时间需要 13 分钟。
转载：http://blog.csdn.net/woshi250hua/article/details/7961869
备注：细心的你可能会注意到：我改了一点点：
(isok[i | (1 << k)])
题目链接:
题目大意:给定n个地点的坐标和每个地点的权值，即一张图n个点，点有点权边有边权。现在裁判在点1，需要分配这些裁判到这些点去，已知每个裁判能够到点权之和不大于m，而且一个点不能由两个裁判访问。现在给出两个问题，1、最少几个裁判可以覆盖所有点 2、给定无数个裁判，怎么样访问这些点使得总边权和最小，裁判访问完必须回到1点，而且一个裁判访问的点权之和不能超过m。
解题思路： 昨天天津赛区的1004题，比赛的时候都想到了算法，就是不敢去敲，一直在想稳妥的算法，最终没有ac。
晚一点和其他学校的acmer交流聊到这题，就想着要不要去试下，如果不行的话明天去搜论文，因为这是很经典的mTSP问题。但是没想到竟然ac了，神奇得ac了，坑爹地ac了，复杂度sigma[C(n,i)*(2^i-1)],最坏情况下计算量也才2000多万，其实是我错了！！ac完想到的第一句话不是终于ac而是：尼玛,中山大学就喜欢这么暴力么?..
有可能不是正解，但还是写下思路，感觉两个问题都很经典。
第一问：求最少的裁判覆盖这些点，思路是先将2^n种地点的选择集合压缩成2^n个物品，物品的权值为集合内的点权之和，如果总和<=m，那么他是一种合法的组合，存起来。这样就得到tot种合法组合，对这tot种组合进行01背包，dp[i]表示容量为i时的最小费用，和常规的背包不同，但本质是一样的。状态转移方程:dp[i] = min(dp[i],dp[j]+1) (j为i的子集,i = j | state[k]并且j和state[k]没有交集，state[k]表示第k个合法物品)
PS：后来发现这一问其实用贪心就可以解决，每次都选最大的，直到本次不能选为止，看能选几次.
第二问：多旅行商问题即mTsp，感觉挺经典的，思路是将mtsp转化成普通的tsp，然后再将各个tsp合并成答案。先要O(2^n*n^2)的预处理得到np[i]表示一个裁判走的集合为i的所有地点又回到最初的点的最少权值和，然后np[i] = min(np[i],np[k|(1<<0)]+np[(i-k)|(1<<0)])(i必须包含0节点，因为子集可能不含0节点，所以要和1<<0或起来，这样才是将两个裁判所走的边权和合并)。
自己默念：
1.首先将能被一个人解决的集合i即可标记为1，即isok【i】=1，之后算出每个该集合访问完毕所需要的 最算时间np【i】，
（这个可以多开一个cost【j】【i】数组来表示：状态i，j最后接入的最小耗费值，这个和单旅行商的解决方案一样了）；
2.最后mTSP和TSP的 区别就在于要将所有的np【i】合并：即np[i] = min(np[i], np[j | 1] + np[(i - j) | 1]);
值得注意的是这里合并后的的isok[i]可以等于0；因为这是 合并后的，即使一个人不能解决完i集合，但是多个人就可以！
#include#include #include #include using namespace std;#define MIN (1<<17)#define MAX 110000#define INF (1<<29)#define min(a,b) ((a)<(b)?(a):(b))int tot, ans1, ans2, n, m; //总合法物品数，第一、第二问答案int x[20], y[20], val[20]; //左边和点权int dp[MAX], state[MIN]; //第一问用到int map[20][20], isok[MIN]; //边权、合法物品集合int cost[17][MIN], np[MIN]; //第二问用到void Initial() { int i, j; tot = 0; memset(map, 0, sizeof (map)); for (i = 0; i < (1 << n); ++i) dp[i] = np[i] = INF; for (i = 0; i <= n; ++i) for (j = 0; j < (1 << n); ++j) cost[i][j] = INF; cost[0][1] = 0;}int cmp1(int a, int b) { return a > b;}int Solve_Tanxin() { int i, j, mmin = INF; int tp[20], vis[20]; for (i = 0; i < n; ++i) vis[i] = 0, tp[i] = val[i]; sort(tp, tp + n, cmp1); for (i = 1; i <= n; ++i) { int rest = m; for (j = 0; j < n; ++j) if (!vis[j] && tp[j] <= rest) rest -= tp[j], vis[j] = 1; ; for (j = 0; j < n && vis[j] == 1; ++j); if (j == n) return i; } return INF;}void GetDist() { for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { double xx = x[i] - x[j]; double yy = y[i] - y[j]; xx *= xx, yy *= yy; map[i][j] = map[j][i] = ceil(sqrt(xx + yy)); }}int ok(int x) { int sum = 0, i; for (i = 0; i < n; ++i) if (x & (1 << i)) sum += val[i]; return sum <= m;}int TSP_Second() { int i, j, k; GetDist(); for (i = 1; i < (1 << n); ++i) if (isok[i]) { for (j = 0; j < n; ++j) if (i & (1 << j)) { np[i] = min(np[i], cost[j][i] + map[j][0]); for (k = 0; k < n; ++k) if (((i & (1 << k)) == 0)&&(isok[i | (1 << k)])) cost[k][i | (1 << k)] = min(cost[k][i | (1 << k)], cost[j][i] + map[j][k]); } } for (i = 1; i < (1 << n); ++i) if (i & 1) for (j = (i - 1) & i; j; j = (j - 1) & i) np[i] = min(np[i], np[j | 1] + np[(i - j) | 1]); return np[(1 << n) - 1];}int main() { int i; while (scanf("%d%d", &n, &m) != EOF) { Initial(); for (i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]); for (i = 0; i < n; ++i) scanf("%d", &val[i]); for (i = 1; i < (1 << n); ++i) { isok[i] = ok(i); if (isok[i]) state[tot++] = i; } ans1 = Solve_Tanxin(); if (ans1 == INF) ans1 = ans2 = -1; else ans2 = TSP_Second(); printf("%d %d\n", ans1, ans2); } return 0;}