昆明建设网站,wordpress设置中改网站,土地推介网,哪个网站可以免费做招牌【题目链接】
洛谷 P1955 [NOI2015] 程序自动分析
【题目考点】
1. 并查集
2. 离散化
【解题思路】
多组数据问题#xff0c;对于每组数据#xff0c;有多个 x i x j x_ix_j xixj或 x i ≠ x j x_i \neq x_j xixj的约束条件。
所有相等的变量构成一个集合对于每组数据有多个 x i x j x_ix_j xixj或 x i ≠ x j x_i \neq x_j xixj的约束条件。
所有相等的变量构成一个集合不相等的变量在不同的集合。可以使用并查集表示集合。 该题的变量编号 i i i或 j j j最大可达到 1 0 9 10^9 109无法直接作为并查集fa数组的下标所以需要先对所有输入的 i i i与 j j j进行离散化。由于每组数据输入的约束条件的数量 n ≤ 1 0 5 n\le 10^5 n≤105每一个约束条件最多新增两个变量编号。因此在对变量编号进行离散化后最多存在 2 ∗ 1 0 5 2*10^5 2∗105个元素离散化后的数值的范围为 1 ∼ 2 ∗ 1 0 5 1\sim 2*10^5 1∼2∗105可以作为fa数组的下标。
先遍历所有约束。对于 x i x j x_i x_j xixj那么可以认为 x i x_i xi与 x j x_j xj同属于一个集合将 x i x_i xi与 x j x_j xj所在的集合合并。再次遍历所有约束对于 x i ≠ x j x_i \neq x_j xixj而且 x i x_i xi与 x j x_j xj已属于同一集合那么该问题中的约束条件无法都被满足输出NO。
当看完所有约束后如果没有输出NO则以上约束条件可以同时满足输出YES。
【题解代码】
#includebits/stdc.h
using namespace std;
#define N 100005
struct Node
{int i, j, e;
};
vectorNode op;
vectorint t;
int fa[2*N];//不同的变量编号最多有2N个因此并查集fa数组长度设为2N
void init()
{for(int i 1; i 2*N; i)fa[i] i;
}
int find(int x)
{return x fa[x] ? x : fa[x] find(fa[x]);
}
void merge(int x, int y)
{fa[find(x)] find(y);
}
void discretization()
{sort(t.begin(), t.end());t.erase(unique(t.begin(), t.end()), t.end());for(Node p : op){p.i upper_bound(t.begin(), t.end(), p.i)-t.begin();//离散化后变量编号范围为1~2*10^5 p.j upper_bound(t.begin(), t.end(), p.j)-t.begin();}
}
bool isMatch()//是否可以满足给定的所有约束
{for(Node p : op) if(p.e 0 find(p.i) find(p.j))return false;return true;
}
int main()
{int tn, n, i, j, e;cin tn;while(tn--){op.clear();t.clear();init();cin n;for(int k 1; k n; k){cin i j e;op.push_back(Node{i, j, e});t.push_back(i);t.push_back(j);}discretization();for(Node p : op) if(p.e 1)//如果是xixj merge(p.i, p.j);cout (isMatch() ? YES : NO) \n;}return 0;
}
