等式发表时间：2022-10-27 20:16 等式 描述 有 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 样例 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"。 输入样例 2 点击下载 限制 对于 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。 时间：2 sec 空间：256 MB 提示 [用并查集来维护相等的集合。] [改编自 NOI 2015 day1 T1 程序自动分析] 代码 #include<iostream> #include<vector> #include<string> using namespace std;
int *Father;
//P.S. "秩"为一棵树的高度的相反数
int Find(int x)//查找某节点的根节点 { int fx;//某节点的根节点(父节点) if (Father[x] > 0)//若x的秩大于0，说明x不是根节点 { fx = Find(Father[x]);//若x不是根节点，则递归查找其根节点 Father[x] = fx;//*****此处至关重要，路径压缩，将某节点的父节点设置为根节点 ******** return fx; } else return x;//若x的秩小于等于0，说明x是根节点，返回x }
void Union(int x, int y)//将x和y所在的两个集合合并 { int fx = Find(x); int fy = Find(y); fy = fy; if (fx == fy && fx != 0)//若fx和fy相等且其两个的秩不为0，则说明他们在同一个集合树中 return; if (Father[fx] < Father[fy]) Father[fy] = fx;//若x所在的集合树比较高，则将y所在的树合并到x所在的树中，即将y 的根节点设置为fx else if (Father[fx] == Father[fy])//若两个树的高度相等，则任意将一个树合并到另一个 树中(此处是将x的根节点设置为fy) { Father[fy] -= 1;//合并后树的高度加一，故秩减一 Father[fx] = fy; } else//若y所在的集合树比较高，则将x所在的树合并到y所在的树中，即将x的根节点设置为fy Father[fx] = fy; }
int main() { int t;//数据组数 cin >> t;
string* ans = new string[t];//存储是否存在方案(Yes或No)
for (int i = 0; i < t; i++) {
ans[i] = "Yes";//先将答案定为Yes，接着通过比较，若不存在方案则将答案从Yes改为No
int n, m;//变量个数和约束条件 cin >> n >> m; Father = new int[n+1]; for (int j = 0; j < n + 1; j++) { Father[j] = 0;//每个元素的初始秩为0 } vector<int> InEqu;//用于存储不相等的元素，以便在最后判断是否存在方案满足所有m 个约束条件 InEqu.resize(2 * m);//设置vector容器大小 int inEqu_num = 0;//用于标记InEqu中有多少个元素 int a, b, e;//e表示a变量和b变量的关系 for (int j = 0; j < m; j++) { cin >> a >> b >> e; if (e == 1 && a != b)//若变量存在对应关系，且两个变量不是同一个数，则合并 集合树 { Union(a, b); } else if (e == 0&&a!=b) //若两个变量不存在对应关系，则压入容器中，在最后查找两个变量的根节 点，若两个变量的根节点一样（且不为0），说明不存在满足约束条件的解，反之则存在 { InEqu.emplace_back(a); InEqu.emplace_back(b); inEqu_num += 2; } else if (e == 0 && a == b)//若两个变量是同一个数且不存在对应关系，则必然无法找出满足约束条件的解 { ans[i] = "No"; continue; } }
//查找InEqu中两个变量的根节点，若两个变量的根节点一样（且不为0），说明不存在满 足约束条件的解，反之则存在 while (inEqu_num != 0) { int fir = InEqu.back(); InEqu.pop_back(); int sec = InEqu.back(); InEqu.pop_back(); inEqu_num -= 2;
int Ffir = Find(fir); int Fsec = Find(sec); if (Ffir == Fsec && Ffir != 0) { ans[i] = "No"; break; } }
}
for (int i = 0; i < t; i++) { cout << ans[i] << endl;//输出答案 }
return 0;
}
|