【算法训练营】等式，道路升级（c++,python实现）-拓冰建站

等式

问题描述

有n个变量和m个“相等”或“不相等”的约束条件，请你判定是否存在一种赋值方案满足所有m个约束条件。

输入格式

第一行一个整数T，表示数据组数。

接下来会有T组数据，对于每组数据：

第一行是两个整数n,m，表示变量个数和约束条件的个数。

接下来m行，每行三个整数a,b,e，表示第a个变量和第b个变量的关系：

若e=0则表示第a个变量不等于第b个变量；
若e=1则表示第a个变量等于第b个变量

输出格式

输出T行，第i行表示第i组数据的答案。若第i组数据存在一种方案则输出"Yes"；否则输出"No"（不包括引号）。

样例1输入

样例1输出

Yes
No

样例1解释

一共有2组数据。

对于第一组数据，有5个约束：

变量1=变量2
变量2=变量3
变量3=变量4
变量1=变量4
变量2≠变量5

显然我们可以令：

变量1=变量2=变量3=变量4=任意一个数值
变量5=任意一个和变量2不同的数值

故第一组数据输出"Yes"。对于第二组数据，有3个约束：

变量1=变量2
变量2=变量3
变量1≠变量3

由前两个约束可推出变量1=变量3，但第三个约束表明变量1≠变量3，矛盾。

故第二组数据输出"No"。

数据范围

对于10%的数据，n,m ≤ 5，T ≤ 5；

对于50%的数据，n,m ≤ 1000，T ≤ 10；

对于100%的数据，1 ≤ n ≤ 300000, m ≤ 500000，1 ≤ a,b ≤ n，T ≤ 100。

保证所有数据的n总和与m总和不超过500000。

时间限制：1 s

空间限制：512 MB

提示

[用并查集来维护相等的集合。]

代码实现

//#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;// 并查集
// ================= 代码实现开始 =================const int N = 300005;//Father:每个节点的父亲节点
//Rank:节点的秩
int Father[N],Rank[N];//查找节点x所在集合的根
//x:节点x
//返回值:根
int find(int x){return Father[x]==x ? x : Father[x]=find(Father[x]);
}// 给定n个变量以及m个约束，判定是否能找出一种赋值方案满足这m个约束条件
// n：如题意
// m：如题意
// A：大小为m的数组，表示m条约束中的a
// B：大小为m的数组，表示m条约束中的b
// E：大小为m的数组，表示m条约束中的e
// 返回值：若能找出一种方案，返回"Yes"；否则返回"No"（不包括引号）。
string getAnswer(int n, int m, vector<int> A, vector<int> B, vector<int> E) {//初始化for(int i = 1; i <= n; ++i){Father[i] = i;Rank[i] = 0;}//需要提前操作e=1的数据,将e=1的数据交换至前面int cnt=0;for(int i = 0; i < m; ++i)if(E[i] == 1){swap(A[i],A[cnt]);swap(B[i],B[cnt]);swap(E[i],E[cnt]);cnt++;}for(int i = 0; i < m; ++i){int setA = find(A[i]); //找到A[i]所在集合的根int setB = find(B[i]); //找到B[i]所在集合的根if(E[i] == 0){if(setA == setB){return "No";}}else{if(setA != setB){  //需要合并的情况//在union时，把rank更高的父节点作为根节点,规定rankB更高一些。if(Rank[setA]>Rank[setB])swap(setA,setB); // 交换A,B集合Father[setA] = setB;if(Rank[setA] == Rank[setB])Rank[setB]+=1;}}}return "Yes";
}// ================= 代码实现结束 =================int main() {int T;for (scanf("%d", &T); T--; ) {int n, m;scanf("%d%d", &n, &m);vector<int> A, B, E;for (int i = 0; i < m; ++i) {int a, b, e;scanf("%d%d%d", &a, &b, &e);A.push_back(a);B.push_back(b);E.push_back(e);}printf("%s\n", getAnswer(n, m, A, B, E).c_str());}return 0;
}

道路升级

问题描述

Z国有 n 个城市和 m 条双向道路，每条道路连接了两个不同的城市，保证所有城市之间都可以通过这些道路互达。每条道路都有一个载重量限制，这限制了通过这条道路的货车最大的载重量。道路的编号从 1 至 m 。巧合的是，所有道路的载重量限制恰好都与其编号相同。

现在，要挑选出若干条道路，将它们升级成高速公路，并满足如下要求：

所有城市之间都可以通过高速公路互达。
对于任意两个城市 u,v 和足够聪明的货车司机：只经过高速公路从 u 到达 v 能够装载货物的最大重量，与经过任意道路从 u 到达 v 能够装载货物的最大重量相等。（足够聪明的司机只关注载重量，并不在意绕路）

在上面的前提下，要求选出的道路数目尽可能少。

求需要挑选出哪些道路升级成高速公路（如果有多种方案请任意输出一种）。

输入

第一行 2 个用空格隔开的整数 n,m ，分别表示城市数目、道路数目。

第 2 行到第 m+1 行，每行 2 个用空格隔开的整数 u,v 描述一条从 u 到 v 的双向道路，第 i+1 行的道路的编号为 i 。

注意：数据只保证不存在连接的城市相同的道路（自环），并不保证不存在两条完全相同的边（重边）

输出

第一行一个整数 k ，表示升级成高速公路的道路数。

接下来 k 行每行一个整数，从小到大输出所有选出的道路的编号。

输入样例

输出样例

2
2
3

数据范围

对于 20% 的数据，保证 n≤5，m≤10。

对于 60% 的数据，保证 n≤1,000，m≤5,000。

对于 100% 的数据，保证 n≤200,000，m≤400,000。

时间限制：10 sec

空间限制：256 MB

提示

[提示1：真的可能有多种方案吗？]

[提示2：k 是否一定为 n-1 呢？（也就是说，选出的道路是否恰好构成了一棵树？）]

[提示3：这道题和最小生成树有什么关系呢？]

代码实现

class UnionSet:def __init__(self, n):self.f = [i for i in range(n + 1)]def find(self, x):if self.f[x] == x:return xself.f[x] = self.find(self.f[x])return self.f[x]def merge(self, x, y):set_x = self.find(x)set_y = self.find(y)if set_x != set_y:self.f[set_x] = set_yreturn Truereturn Falsedef get_answer(n, m, U, V):ans = []us = UnionSet(n)for i in range(m - 1, -1, -1):if us.merge(U[i], V[i]):ans.append(i + 1)ans.reverse()return ansif __name__ == "__main__":n, m = map(int, input().split())U, V = [], []for _ in range(m):u, v = map(int, input().split())U.append(u)V.append(v)ans = get_answer(n, m, U, V)print(len(ans))for edge in ans:print(edge)