苏州网站建设 公司,如何本地搭建自己的网站,广告设计公司简介内容,微信小程序开发入门教程目录
修复公路#xff08;带扩展域的并查集#xff09; 食物链#xff08;带边权的并查集#xff09; 修复公路#xff08;带扩展域的并查集#xff09;
洛谷#xff1a;修复公路https://www.luogu.com.cn/problem/P1111
题目背景
A 地区在地震过后#xff0c;连接…目录
修复公路带扩展域的并查集 食物链带边权的并查集 修复公路带扩展域的并查集
洛谷修复公路https://www.luogu.com.cn/problem/P1111
题目背景
A 地区在地震过后连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述
给出 A 地区的村庄数 N和公路数 M公路是双向的。并告诉你每条公路的连着哪两个村庄并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车即最早什么时候任意两条村庄都存在至少一条修复完成的道路可以由多条公路连成一条道路。
输入格式
第 11 行两个正整数 N,M。
下面 M 行每行 3 个正整数 x,y,t告诉你这条公路连着 x,y 两个村庄在时间t时能修复完成这条公路。
输出格式
如果全部公路修复完毕仍然存在两个村庄无法通车则输出 −1否则输出最早什么时候任意两个村庄能够通车。
输入输出样例
输入 #1复制
4 4
1 2 6
1 3 4
1 4 5
4 2 3
输出 #1复制
5
思路
当合并一次之后我们扫一遍fa数组统计fa[i]i的个数
如果只有1个fa[i]i就说明所有的全部联通了因为只有1个人是自己的祖先别的人都跟着他如果不止1个就说明当前没有全部联通因为两个人互相没有关系需要继续合并。
// Problem: A - 修复公路
// Contest: Virtual Judge - 2023暑期训练-高级数据结构 Part1
// URL: https://vjudge.net/contest/571187#problem/A
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.h
using namespace std;typedef long long ll;const int N 2e55;int n,m;
int f[N];
int num;
int ans;struct node{int a,b,t;
}e[N];bool cmp(node x,node y){return x.ty.t;
}int find(int x){if(x!f[x]) return find(f[x]);return f[x];
}int main(){cinnm;for(int i1;in;i){f[i]i;}for(int i1;im;i){cine[i].ae[i].be[i].t;}sort(e1,e1m,cmp);for(int i1;im;i){int xfind(e[i].a),yfind(e[i].b);if(xy) continue;f[x]y;num;anse[i].t;}if(num!n-1) cout-1\n;else coutans\n;return 0; } 食物链带边权的并查集
洛谷食物链https://www.luogu.com.cn/problem/P2024
题目描述
动物王国中有三类动物 A,B,C这三类动物的食物链构成了有趣的环形。A 吃 BB 吃 CC 吃 A。
现有 N 个动物以 1∼N 编号。每个动物都是 A,B,C 中的一种但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述
第一种说法是 1 X Y表示 X 和 Y 是同类。第二种说法是2 X Y表示 X 吃 Y。
此人对 N 个动物用上述两种说法一句接一句地说出 K 句话这 K 句话有的是真的有的是假的。当一句话满足下列三条之一时这句话就是假话否则就是真话。
当前的话与前面的某些真的话冲突就是假话当前的话中 X 或 Y 比 N 大就是假话当前的话表示 X 吃 X就是假话。
你的任务是根据给定的 N 和 K 句话输出假话的总数。
输入格式
第一行两个整数N,K表示有 N 个动物K 句话。
第二行开始每行一句话按照题目要求见样例
输出格式
一行一个整数表示假话的总数。
输入输出样例
输入 #1复制
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5输出 #1复制
3
思路 // Problem: E - 食物链
// Contest: Virtual Judge - 2023暑期训练-高级数据结构 Part1
// URL: https://vjudge.net/contest/571187#problem/E
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.h
using namespace std;typedef long long ll;const int N 2e55;int n,m;
int p[N];
int d[N];int find(int x){if(x!p[x]){int up[x]; p[x]find(p[x]);d[x]d[u]; }return p[x];
}int main(){cinnm;for(int i1;in;i){p[i]i;}int res0;for(int i1;im;i){int t,x,y;cintxy;if(xn||yn) res;else{int pxfind(x),pyfind(y);if(t1){if(pxpy(d[x]-d[y])%3){res;}else if(px!py){p[px]py;d[px]d[y]-d[x];}}else{if(pxpy(d[x]-d[y]-1)%3){res;}else if(px!py){p[px]py;d[px]d[y]1-d[x];}}}}coutres\n;return 0; }
