題目大意:給定n個地點的坐標和每個地點的權值，即一張圖n個點，點有點權邊有邊權。現在裁判在點1，需要分配這些裁判到這些點去，已知每個裁判能夠到點權之和不大於m，而且一個點不能由兩個裁判訪問。現在給出兩個問題，1、最少幾個裁判可以覆蓋所有點 2、給定無數個裁判，怎麼樣訪問這些點使得總邊權和最小，裁判訪問完必須回到1點，而且一個裁判訪問的點權之和不能超過m。
解題思路： 昨天天津賽區的1004題，比賽的時候都想到了算法，就是不敢去敲，一直在想穩妥的算法，最終沒有ac。
晚一點和其他學校的acmer交流聊到這題，就想著要不要去試下，如果不行的話明天去搜論文，因為這是很經典的mTSP問題。但是沒想到竟然ac了，神奇得ac了，坑爹地ac了，復雜度O(2^(2*n)+(2^n*n^2))，排名還很靠前。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或起來，這樣才是將兩個裁判所走的邊權和合並)。
測試數據：
Input:
3 3
0 0
0 3
0 4
0
2
2
3 2
0 0
0 3
1 0
0
1
2
3 1
0 0
0 3
0 1
0
1
2
4 9
1 2
1 3
2 1
3 1
0
5
6
4
16 3500
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69
0
19
30
16
23
11
31
15
28
8
8
7
14
6
19
11
Input:
2 14
2 8
-1 -1
2 11
1 164
代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
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, k;
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, k, 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;
}
int Solve_First() {
int i, j, k, mmin = INF;
dp[0] = 0;
for (i = 0; i < tot; ++i)
for (j = (1 << n) - 1; j >= 0; --j) {
if (dp[j] == INF) continue;
int st = j + state[i];
if (st != (j | state[i])) continue;
dp[st] = min(dp[st], dp[j] + 1);
}
return dp[(1 << n) - 1];
}
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)
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, j, k;
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();
//ans1 = Solve_First();
if (ans1 == INF)
ans1 = ans2 = -1;
else ans2 = TSP_Second();
printf("%d %d\n", ans1, ans2);
}
}
