给出一棵树， 树上点的值为0或1， 可以交换树上两个点的权值， 给出一个距离m， 所有的0距离最近的1的距离不能超过m， 求最少的交换次数。
首先对于每一个点u，所有离u的距离不超过m的点v， 加一条边（u, v)。
然后dlx， 剪枝的函数是当前1的个数+还需要的1的个数不超过1的总数， 具体看代码。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 const int maxn = 200; 20 const int maxNode = 10000; 21 int head[maxn], num; 22 struct node 23 { 24 int to, nextt, c; 25 }e[maxn]; 26 void addEdge(int u, int v, int c) { 27 e[num].to = v; 28 e[num].nextt = head[u]; 29 e[num].c = c; 30 head[u] = num++; 31 } 32 struct DLX { 33 int L[maxNode], R[maxNode], U[maxNode], D[maxNode], row[maxNode], col[maxNode]; 34 int S[maxn], H[maxn], deep, ans[maxn], sz, n, m, kind[maxn], boy_num; 35 void remove(int c) { 36 for(int i = D[c]; i!=c; i = D[i]) { 37 L[R[i]] = L[i]; 38 R[L[i]] = R[i]; 39 } 40 } 41 void resume(int c) { 42 for(int i = U[c]; i!=c; i = U[i]) { 43 L[R[i]] = i; 44 R[L[i]] = i; 45 } 46 } 47 int h() { 48 int cnt = 0; 49 int vis[105]; 50 mem(vis); 51 for(int i = R[0]; i!=0; i = R[i]) { 52 if(!vis[i]) { 53 cnt++; 54 vis[i] = 1; 55 for(int j = D[i]; j!=i; j = D[j]) { 56 for(int k = R[j]; k!=j; k = R[k]) { 57 vis[col[k]] = 1; 58 } 59 } 60 } 61 } 62 return cnt; 63 } 64 void dfs(int d, int cnt) { 65 if(d+h()>boy_num||cnt>=deep) 66 return ; 67 if(R[0] == 0) { 68 deep = min(deep, cnt); 69 return ; 70 } 71 int c = R[0]; 72 for(int i = R[0]; i!=0; i = R[i]) 73 if(S[c]>S[i]) 74 c = i; 75 for(int i = D[c]; i!=c; i = D[i]) { 76 remove(i); 77 for(int j = R[i]; j!=i; j = R[j]) 78 remove(j); 79 dfs(d+1, cnt+(!kind[row[i]])); 80 for(int j = L[i]; j!=i; j = L[j]) 81 resume(j); 82 resume(i); 83 } 84 return ; 85 } 86 void add(int r, int c) { 87 sz++; 88 row[sz] = r; 89 col[sz] = c; 90 S[c]++; 91 U[sz] = U[c]; 92 D[sz] = c; 93 D[U[c]] = sz; 94 U[c] = sz; 95 if(~H[r]) { 96 R[sz] = H[r]; 97 L[sz] = L[H[r]]; 98 L[R[sz]] = sz; 99 R[L[sz]] = sz; 100 } else { 101 H[r] = L[sz] = R[sz] = sz; 102 } 103 } 104 void init(){ 105 mem1(H); 106 num = boy_num = 0; 107 mem1(head); 108 deep = inf; 109 for(int i = 0; i<=n; i++) { 110 R[i] = i+1; 111 L[i] = i-1; 112 U[i] = i; 113 D[i] = i; 114 } 115 mem(S); 116 R[n] = 0; 117 L[0] = n; 118 sz = n; 119 } 120 void dfs(int u, int root, int fa, int d) { 121 add(root, u); 122 for(int i = head[u]; ~i; i = e[i].nextt) { 123 int v = e[i].to, c = e[i].c; 124 if(v == fa) 125 continue; 126 if(c+d<=m) 127 dfs(v, root, u, d+c); 128 } 129 } 130 void solve() { 131 init(); 132 int u, v, c; 133 for(int i = 1; i<=n; i++) { 134 scanf("%d", &kind[i]); 135 boy_num+=kind[i]; 136 } 137 for(int i = 0; i<n-1; i++) { 138 scanf("%d%d%d", &u, &v, &c); 139 addEdge(u, v, c); 140 addEdge(v, u, c); 141 } 142 for(int i = 1; i<=n; i++) { 143 dfs(i, i, -1, 0); 144 } 145 dfs(0, 0); 146 if(deep == inf) 147 deep = -1; 148 cout<<deep<<endl; 149 } 150 }dlx; 151 int main() 152 { 153 int t; 154 cin>>t; 155 for(int i = 1; i<=t; i++) { 156 printf("Case #%d: ", i); 157 scanf("%d%d", &dlx.n, &dlx.m); 158 dlx.solve(); 159 } 160 return 0; 161 }