这东西以前觉得挺难的,但是那是因为没好好学。
我不会告诉你我是因为订正模拟赛的需要才好好学了一遍qwq
我觉得这种优化还是借助题目来学习,更加容易理解(而且不难)。
P2619 [国家集训队] Tree I
虽然说是 dp 优化,但是我感觉这道题好像没有 dp。
不妨设它需要 \(ned\) 条边。
首先考虑没有白边限制的情况下,这里有一个高妙的算法就是:并查集。
然后我们令 \(f_x\) 表示白边数量是 \(x\) 的最小生成树,接着我们发现这种东西一定是先下降一段,再上升一段。
所以我们将 \((x,f_x)\) 画在二维平面上,盲猜它形成下凸包的图形(这是题解告诉我的qwq)。
考虑用一个斜率 \(k\) 去切这个图形,则切点所对应的直线的截距一定是最小的,即:
显然对于每个点 \((x,f_x)\),且截距应该是 \(g_x = f_x - k \times x\)。
对于 \(g_x\) 的意义,就是每条白边的边权减少 \(k\),白边数量是 \(x\) 的最小生成树。
而 \(g_x\) 最小,固然就是:每条白边边权减少 \(k\) 后,整个图的最小生成树。
记录一下最小生成树所选的白边数量 \(p\),可以得到斜率为 \(k\) 的直线切这个图形的交点 \((p,f_p)\)。
所以呢,现在就考虑如何找到斜率 \(k\),使得我们可以得到 \(f_{ned}\),wqs二分这个知识点告诉我们,也许可以二分。
跟着斜率 \(k\) 的增大,我们可以发现切点也是不断增大,所以可以直接二分找到这个斜率 \(k\),就能求出 \(f_{ned}\)。
有一种情况就是,图形可能出现三点共线的情况,比如 \(x,ned,y\) 而对于这种情况,我们只需要在贪心的时候选优先选白边即可,因为我们二分是找到最小的可以选择的斜率,而对于 \(y\) 最小可以选择的斜率,由三点共线可得,一定是这三个点所组成的斜率,故而 \(ned\) 也是可以选择这个斜率的。
代码异常好些qwq
#include <bits/stdc++.h>
using namespace std;
int rd() {
int x = 0, f = 1;
char ch = getchar();
while (!('0' <= ch && ch <= '9')) {
if (ch == '-') f = -1; ch = getchar();
}
while ('0' <= ch && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();
}
return x * f;
}
void wr(int x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) wr(x / 10); putchar(x % 10 + '0');
}
const int N = 1e5 + 10;
struct union_find {
int n, f[N];
void init(int nn) {
n = nn; for (int i = 1; i <= n; ++i) f[i] = i;
}
int find (int x) {
if (f[x] == x) return x;
return f[x] = find(f[x]);
}
bool merge (int x, int y) {
if (find(x) == find(y)) return false;
f[find(x)] = find(y); return true;
}
} T;
struct node {
int u, v, w, col;
node (int uu = 0, int vv = 0, int ww = 0, int coll = 0) {
u = uu; v = vv; w = ww; col = coll;
}
bool operator < (const node res) const {
if (w != res.w) return w < res.w;
return col < res.col;
}
} p[N];
int n, m, ned;
int u[N], v[N], w[N], col[N];
pair<int,int> check (int x) {
for (int i = 1; i <= m; ++i) {
if (col[i] == 0) p[i] = node(u[i], v[i], w[i] - x, col[i]);
else p[i] = node(u[i], v[i], w[i], col[i]);
}
sort (p + 1, p + m + 1); T.init(n);
int num = 0, sum = 0;
for (int i = 1; i <= m; ++i) {
if (T.merge (p[i].u, p[i].v)) num += (!p[i].col), sum += p[i].w;
}
return make_pair(num,sum);
}
int main() {
n = rd(); m = rd(); ned = rd();
for (int i = 1; i <= m; ++i) u[i] = rd(), v[i] = rd(), w[i] = rd(), col[i] = rd();
for (int i = 1; i <= m; ++i) ++u[i], ++v[i];
int l = -100, r = 100;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid).first >= ned) r = mid; else l = mid + 1;
}
printf ("%d\n", check(l).second + ned * l);
return 0;
}
总结
总之,wqs二分就是:没有限制的时候好做,加上限制后是凸的。
至于凸的怎么证,打打表猜一猜也许可行?(反正我不会其他方法qwq)。