题解【洛谷P2619】[国家集训队2]Tree I

题目描述

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有\(need\)条白色边的生成树。

题目保证有解。

输入输出格式

输入格式

第一行\(V,E,need\)分别表示点数，边数和需要的白色边数。

接下来\(E\)行

每行\(s,t,c,col\)表示这边的端点(点从\(0\)开始标号)，边权，颜色(\(0\)白色\(1\)黑色)。

输出格式

一行表示所求生成树的边权和。

输入输出样例

输入样例#1

输出样例#1

说明

\(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;//结束

}

巴特西