JDK动态代理 测试用例 springcloud docker安装部署 map遍历 iphone dart inheritance deployment 逻辑端口 safari ios4 ionic3 ionic framework vue下载 vue树形菜单 matlab 图像识别 leach算法 mac上传文件到linux mysql分页查询sql语句 mysql自然连接 java 注解 mysql 选择数据库 python中assert 安装python教程 python命令行 python中的range函数 java接口类 java学习文档 java获取ip地址 java单继承 java新建文件 java包名 java重命名 java网课 linux用户管理 小程序源码下载 python的用途 js格式化时间 3dmax插件神器
当前位置: 首页 > 学习教程  > 编程语言

CodeForces - 1468J - Road Reform

2021/2/13 16:20:17 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

Road Reform 题意 给你一个 nnn 个顶点 mmm 条边的无向图 (没有重边) 要求删掉 m−(n−1)m - (n - 1)m−(n−1) 条边使得图仍联通 并且权值最大的边与 kkk 的差值最小 思路 先把所有小于等于 kkk 的边加入新图 然后判断是否连通 如果已经联通 那么有两种选择 ​ 1.将已经…

Road Reform

题意

给你一个 n n n 个顶点 m m m 条边的无向图 (没有重边) 要求删掉 m − ( n − 1 ) m - (n - 1) m(n1) 条边使得图仍联通 并且权值最大的边与 k k k 的差值最小

思路

先把所有小于等于 k k k 的边加入新图 然后判断是否连通

如果已经联通 那么有两种选择

​ 1.将已经加入的最大边权增大到 k k k

​ 2.将大于 k k k 的第一条边加入 并且减少到 k k k

如果没有联通 那么按照边权递增的顺序加入边 直到联通为止

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
using namespace std;

typedef  long long LL;
typedef pair<int, int>PII;
inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
const int N = 200010;

int n, m, k;
int f[N];

struct Node {
	int u, v, w;
}node[N];

void init() {
	for (int i = 0; i < N; ++i)f[i] = i;
}

int Find(int x) {
	return x == f[x] ? x : f[x] = Find(f[x]);
}

void merge(int a, int b) {
	f[Find(a)] = Find(b);
}

bool cmp(Node a, Node b) {
	return a.w < b.w;
}

void solve() {
	cin >> n >> m >> k;
	init();

	for (int i = 1; i <= m; ++i) {
		int a, b, c; scanf("%d%d%d", &node[i].u, &node[i].v, &node[i].w);
	}

	sort(node + 1, node + m + 1, cmp);

	int cnt = 0;
	int i;
	for (i = 1; i <= m; ++i) {
		if (node[i].w > k)break;

		int fa = Find(node[i].u);
		int fb = Find(node[i].v);

		if (fa != fb) {
			merge(fa, fb);
			cnt++;
		}
	}

	//cout << node[i - 1].w << " " << node[i].w << endl;
	if (cnt == n - 1) {
		int res = k - node[i - 1].w;
		if (i <= m)res = min(res, node[i].w - k);
		printf("%d\n", res);
	}
	else {
		LL res = 0;
		for (int j = i; j <= m; ++j) {
			int fa = Find(node[j].u);
			int fb = Find(node[j].v);

			if (fa != fb) {
				cnt++;
				merge(fa, fb);
				res += node[j].w - k;
			}

			if (cnt == n - 1)break;
		}

		cout << res << endl;
	}
}

int main() {
	int t; cin >> t;
	while(t--)
		solve();

	return 0;
}

本文链接: http://www.dtmao.cc/news_show_700017.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?