题目描述
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有\(need\)条白色边的生成树。
题目保证有解。
输入输出格式
输入格式
第一行\(V,E,need\)分别表示点数，边数和需要的白色边数。
接下来\(E\)行
每行\(s,t,c,col\)表示这边的端点(点从\(0\)开始标号)，边权，颜色(\(0\)白色\(1\)黑色)。
输出格式
一行表示所求生成树的边权和。
输入输出样例
输入样例#1
2 2 1
0 1 1 1
0 1 2 0
输出样例#1
2
说明
\(0:V<=10\)
\(1,2,3:V<=15\)
\(0,..,19:V<=50000,E<=100000\)
所有数据边权为\([1,100]\)中的正整数。
\(By\) \(WJMZBMR\)
题解
\(WQS\)二分入门题。
关于\(WQS\)二分，可以把这里作为教程，做一下这里的练习题。
回到这个题，我们可以将\(WQS\)二分和\(MST\)（最小生成树）配合解题。
考虑给每一条白边减去一个值\(cost\)，使得在坐标轴上横坐标为\(k\)的点纵坐标最大。
二分\(cost\)，将每一条白边减去\(cost\)，最后用\(Kruskal\)跑一遍\(MST\)即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
int n, m, k, sum, tot, cnt, ans;
int uu[100003], vv[100003], ww[100003], cc[100003], fa[100003];
struct Node
{
int u, v, w, c;
} e[100003];
inline bool cmp(Node x, Node y)//将点权排序
{
if (x.w == y.w) return x.c > y.c;
else return x.w < y.w;
}
int getf(int u)//并查集找祖先
{
if (fa[u] == u) return u;
return fa[u] = getf(fa[u]);
}
inline bool check(int t)//二分的check
{
tot = cnt = 0;//将计数器清零
for (int i = 1; i <= n; i++) fa[i] = i;//初始化祖先
for (int i = 1; i <= m; i++)//存图
{
e[i].u = uu[i], e[i].v = vv[i], e[i].c = cc[i], e[i].w = ww[i];
if (!cc[i]) e[i].w = e[i].w - t;//白边减去边权
}
sort(e + 1, e + 1 + m, cmp);//将边排序
for (int i = 1; i <= m; i++)//跑一遍MST
{
int p = getf(e[i].u), q = getf(e[i].v);
if (p != q)
{
fa[p] = q, tot = tot + e[i].w;
if (!e[i].c) ++cnt;//是白色边就计数器+1
}
}
return cnt <= k;//符合题目条件
}
int main()
{
n = gi(), m = gi(), k = gi();
for (int i = 1; i <= m; i++)
{
uu[i] = gi(), vv[i] = gi(), ww[i] = gi(), cc[i] = gi();
++uu[i], ++vv[i];
}//输入
int Left = -105, Right = 105;
while (Left <= Right)//开始二分
{
int mid = (Left + Right) >> 1;
if (check(mid))
{
Left = mid + 1, ans = tot + k * mid;//注意ans的存储
}
else
{
Right = mid - 1;
}
}
printf("%d\n", ans);//输出ans
return 0;//结束
}