LYDSY 1196
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
#include <cstring>
int fa[10010], X[20010], Y[20010], C1[20010], C2[20010], n, k, m;
int Find(int x) { return fa[x] == -1 ? x : fa[x] = Find(fa[x]); }
bool check(int x)
{
memset(fa, -1, sizeof(fa));
int cnt1 = 0, cnt2 = 0;
for (int i = 1, fx, fy; i < m; i++)
if ((C1[i] <= x) && ((fx = Find(X[i])) != (fy = Find(Y[i]))))
cnt1++, fa[fx] = fy;
for (int i = 1, fx, fy; i < m; i++)
if ((C2[i] <= x) && ((fx = Find(X[i])) != (fy = Find(Y[i]))))
cnt2++, fa[fx] = fy;
return cnt1 >= k && cnt1 + cnt2 == n - 1;
}
int main()
{
scanf("%d%d%d", &n, &k, &m);
for (int i = 1; i < m; i++)
scanf("%d%d%d%d", X + i, Y + i, C1 + i, C2 + i);
int l = 0, r = 0x3f3f3f3f, mid;
while (l < r) check(mid = (l + r) >> 1) ? r = mid : l = mid + 1;
printf("%d", l);
return 0;
}