wqs二分常用来解决这样的问题：在某个限定条件 (k) 下，求最大/最小值。
wqs二分就是先不管条件 (k) ,看这时取到最值的情况下条件满足的怎么样，然后对和这个条件有关，能影响到最值的部分二分加权，再看满足的怎么样。
这道题的话我们先二分一个权值 (val) ,让和 (s) 相连的边都加上 (val) ,看最后选了多少条和 (s) 相连的边，再根据这个调整 (val).
套上一个克鲁斯卡尔生成树就完了。注意这题判无解的情况。
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n, m, s, k, x, y, z, tot0, tot1, tmp, l, r, mid, ans, cnt;
long long res;
const int N = 50005, M = 500005, inf = 1e9;
int fa[N];
struct bian
{
int x, y, z, is;
friend bool operator <(const bian &a, const bian &b) {return a.z < b.z;}
} b[2][M], e[M];
int find(int x) {return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);}
void he(int x, int y) {fa[find(x)] = fa[find(y)];}
int check(int mid)
{
for (int i = 1; i <= tot1; ++i)b[1][i].z += mid;
int i, j, o; i = j = o = 0;
while (i < tot0 && j < tot1)
{
if (b[0][i + 1] < b[1][j + 1])e[++o] = b[0][++i];
else e[++o] = b[1][++j];
}
while (i < tot0)e[++o] = b[0][++i];
while (j < tot1)e[++o] = b[1][++j];
for (int i = 1; i <= tot1; ++i)b[1][i].z -= mid;
res = cnt = 0;
for (int i = 1; i <= n; ++i)fa[i] = i;
for (int i = 1, js = 0; i <= m; ++i)
{
x = e[i].x; y = e[i].y;
if (find(x) == find(y))continue;
he(x, y);
if (e[i].is)++cnt;
res += e[i].z;
if ((++js) == n - 1)break;
}
return cnt >= k;
}
int main()
{
cin >> n >> m >> s >> k;
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &x, &y, &z);
if (x == s || y == s)b[1][++tot1] = (bian) {x, y, z, 1};
else b[0][++tot0] = (bian) {x, y, z, 0};
}
if (tot1 < k)return puts("Impossible") == 2333;
for (int i = 1; i <= n; ++i)fa[i] = i;
tmp = n;
for (int i = 1; i <= tot0; ++i)
if (find(b[0][i].x) != find(b[0][i].y))he(b[0][i].x, b[0][i].y), --tmp;
for (int i = 1; i <= tot1; ++i)
if (find(b[1][i].x) != find(b[1][i].y))he(b[1][i].x, b[1][i].y), --tmp;
if (tmp > 1)return puts("Impossible") == 2333;
sort(b[0] + 1, b[0] + 1 + tot0); sort(b[1] + 1, b[1] + 1 + tot1);
l = -inf; r = inf; ans = l;
if (!check(l))return puts("Impossible") == 2333;
while (l <= r)
{
mid = (l + r) >> 1;
if (check(mid))ans = mid, l = mid + 1;
else r = mid - 1;
}
check(ans);
if (cnt != k)puts("Impossible");
else cout << res - (long long)k*ans;
return 0;
}