题意：树上最长不相交k条链。
1 #include2 #include 3 #include 4 5 typedef long long LL; 6 const int N = 300010; 7 8 struct Edge { 9 int nex, v;10 LL len;11 }edge[N << 1]; int top;12 13 LL f[N][110][3];14 int e[N], n, k, siz[N];15 16 inline void add(int x, int y, LL z) {17 top++;18 edge[top].v = y;19 edge[top].len = z;20 edge[top].nex = e[x];21 e[x] = top;22 return;23 }24 25 inline void exmax(LL &a, LL b) {26 if(a < b) {27 a = b;28 }29 return;30 }31 32 void DFS(int x, int fa) {33 siz[x] = 1;34 f[x][0][0] = 0;35 for(int i = e[x]; i; i = edge[i].nex) {36 int y = edge[i].v;37 if(y == fa) {38 continue;39 }40 DFS(y, x);41 siz[x] += siz[y];42 // DP43 for(int j = std::min(k, siz[x]); j >= 1; j--) {44 for(int p = 0; p <= j && p <= siz[y]; p++) { // p in son45 exmax(f[x][j][2], f[x][j - p + 1][1] + f[y][p][1] + edge[i].len);46 exmax(f[x][j][0], f[x][j - p][0] + std::max(f[y][p][2], std::max(f[y][p][0], f[y][p][1])));47 exmax(f[x][j][1], f[x][j - p][1] + std::max(f[y][p][2], std::max(f[y][p][0], f[y][p][1])));48 exmax(f[x][j][2], f[x][j - p][2] + std::max(f[y][p][2], std::max(f[y][p][0], f[y][p][1])));49 exmax(f[x][j][1], f[x][j - p][0] + f[y][p][1] + edge[i].len);50 }51 }52 }53 for(int i = 1; i <= k && i <= siz[x]; i++) {54 exmax(f[x][i][1], f[x][i - 1][0]);55 }56 /*printf("x = %d \n", x);57 for(int i = 0; i <= k && i <= siz[x]; i++) {58 printf("%d || 0 : %lld 1 : %lld 2 : %lld \n", i, f[x][i][0], f[x][i][1], f[x][i][2]);59 }*/60 return;61 }62 63 int main() {64 int n;65 memset(f, ~0x3f, sizeof(f));66 scanf("%d%d", &n, &k);67 k++;68 int x, y;69 LL z;70 for(int i = 1; i < n; i++) {71 scanf("%d%d%lld", &x, &y, &z);72 add(x, y, z);73 add(y, x, z);74 }75 DFS(1, 0);76 printf("%lld\n", std::max(std::max(f[1][k][0], f[1][k][1]), f[1][k][2]));77 return 0;78 }
解：带权二分/wqs二分/DP凸优化。
一个比较常见的套路吧。
一般是求解有k限制的最优化问题。且随着k的变化，极值函数上凸/下凸。
这时我们二分一个斜率去切它，会有一个斜率切到我们要的k。
感性理解一下，我们给这k个事物附上权值，然后权值增加的时候k就会变多，权值减小(可以为负)的时候k会变少。
然后会有某个权值使得不限制k时的最优值恰好选了k。这时候我们减去附加的权值即可。
本题就是给每条链加上一个权值。
还有一道题是k条白边，剩下的选黑边的最小生成树。
1 #include2 #include 3 #include 4 #include 5 6 typedef long long LL; 7 const int N = 300010; 8 const LL INF = 1e17; 9 10 struct Edge {11 int nex, v;12 LL len;13 }edge[N << 1]; int top;14 15 LL f[N][3], D;16 int g[N][3], n, k, e[N];17 18 inline void add(int x, int y, LL z) {19 top++;20 edge[top].v = y;21 edge[top].len = z;22 edge[top].nex = e[x];23 e[x] = top;24 return;25 }26 27 inline void exmax(LL &a, int &c, LL b, int d) {28 if(a < b || (a == b && c > d)) {29 a = b;30 c = d;31 }32 return;33 }34 35 void DFS(int x, int fa) {36 f[x][0] = 0; // 初始化 不选链37 for(int i = e[x]; i; i = edge[i].nex) {38 int y = edge[i].v;39 if(y == fa) {40 continue;41 }42 DFS(y, x);43 exmax(f[x][2], g[x][2], f[x][2] + f[y][2], g[x][2] + g[y][2]);44 exmax(f[x][2], g[x][2], f[x][1] + f[y][1] + edge[i].len - D, g[x][1] + g[y][1] - 1); // 1 -> 245 46 exmax(f[x][1], g[x][1], f[x][1] + f[y][2], g[x][1] + g[y][2]);47 exmax(f[x][1], g[x][1], f[x][0] + f[y][1] + edge[i].len, g[x][0] + g[y][1]); // 0 -> 148 49 exmax(f[x][0], g[x][0], f[x][0] + f[y][2], g[x][0] + g[y][2]);50 }51 exmax(f[x][1], g[x][1], f[x][0] + D, g[x][0] + 1); // 自己单独开链52 exmax(f[x][2], g[x][2], f[x][1], g[x][1]);53 exmax(f[x][2], g[x][2], f[x][0], g[x][0]);54 return;55 }56 57 inline bool check(LL mid) {58 D = mid;59 memset(g, 0, sizeof(g));60 memset(f, ~0x3f, sizeof(f));61 DFS(1, 0);62 //printf("D = %lld \nf = %lld g = %d \n\n", D, f[1][2], g[1][2]);63 return 0;64 }65 66 int main() {67 68 scanf("%d%d", &n, &k);69 LL z, r = 10, l;70 k++;71 for(int i = 1, x, y; i < n; i++) {72 scanf("%d%d%lld", &x, &y, &z);73 add(x, y, z);74 add(y, x, z);75 r += std::abs(z);76 }77 l = -r;78 while(l < r) {79 LL mid = (l + r + 1) >> 1;80 //printf("%lld %lld mid = %lld \n", l, r, mid);81 check(mid);82 if(g[1][2] == k) {83 printf("%lld\n", f[1][2] - k * mid);84 return 0;85 }86 if(g[1][2] > k) {87 r = mid - 1;88 }89 else {90 l = mid;91 }92 }93 94 check(r);95 printf("%lld\n", f[1][2] - k * r);96 return 0;97 }
本题只要整数二分就行了。
负数二分用右移，是向下取整。
细节：可能最优点不是凸包上的顶点，是一条边中间。我们这时找到靠左的那个顶点，然后用这个斜率 * k就行了。
实数版：
1 #include2 #include 3 #include 4 #include 5 6 typedef long long LL; 7 const int N = 300010; 8 const LL INF = 1e17; 9 const double eps = 1e-6; 10 11 struct Edge { 12 int nex, v; 13 LL len; 14 }edge[N << 1]; int top; 15 16 double f[N][3], D; 17 int g[N][3], n, k, e[N]; 18 19 inline void add(int x, int y, LL z) { 20 top++; 21 edge[top].v = y; 22 edge[top].len = z; 23 edge[top].nex = e[x]; 24 e[x] = top; 25 return; 26 } 27 28 inline void exmax(double &a, int &c, double b, int d) { 29 // if(a < b || (a == b && c > d)) { 30 if(a < b) { 31 a = b; 32 c = d; 33 } 34 return; 35 } 36 37 void DFS(int x, int fa) { 38 f[x][0] = 0; // 初始化 不选链 39 for(int i = e[x]; i; i = edge[i].nex) { 40 int y = edge[i].v; 41 if(y == fa) { 42 continue; 43 } 44 DFS(y, x); 45 exmax(f[x][2], g[x][2], f[x][2] + f[y][2], g[x][2] + g[y][2]); 46 exmax(f[x][2], g[x][2], f[x][1] + f[y][1] + edge[i].len - D, g[x][1] + g[y][1] - 1); // 1 -> 2 47 48 exmax(f[x][1], g[x][1], f[x][1] + f[y][2], g[x][1] + g[y][2]); 49 exmax(f[x][1], g[x][1], f[x][0] + f[y][1] + edge[i].len, g[x][0] + g[y][1]); // 0 -> 1 50 51 exmax(f[x][0], g[x][0], f[x][0] + f[y][2], g[x][0] + g[y][2]); 52 } 53 exmax(f[x][1], g[x][1], f[x][0] + D, g[x][0] + 1); // 自己单独开链 54 exmax(f[x][2], g[x][2], f[x][1], g[x][1]); 55 exmax(f[x][2], g[x][2], f[x][0], g[x][0]); 56 return; 57 } 58 59 inline bool check(double mid) { 60 D = mid; 61 memset(g, 0, sizeof(g)); 62 //memset(f, ~0x3f, sizeof(f)); 63 for(int i = 1; i <= n; i++) { 64 f[i][0] = f[i][1] = f[i][2] = -INF; 65 } 66 DFS(1, 0); 67 //printf("D = %lld \nf = %lld g = %d \n\n", D, f[1][2], g[1][2]); 68 return 0; 69 } 70 71 int main() { 72 73 scanf("%d%d", &n, &k); 74 LL z; 75 double r = 10, l; 76 k++; 77 for(int i = 1, x, y; i < n; i++) { 78 scanf("%d%d%lld", &x, &y, &z); 79 add(x, y, z); 80 add(y, x, z); 81 r += std::abs(z); 82 } 83 l = -r; 84 while(fabs(r - l) > eps) { 85 double mid = (l + r) / 2; 86 //printf("%lld %lld mid = %lld \n", l, r, mid); 87 check(mid); 88 if(g[1][2] == k) { 89 printf("%.0f\n", f[1][2] - k * mid); 90 return 0; 91 } 92 if(g[1][2] > k) { 93 r = mid; 94 } 95 else { 96 l = mid; 97 } 98 } 99 100 check(r);101 printf("%.0f\n", f[1][2] - k * r);102 return 0;103 }