c/c++语言开发共享BZOJ4602: [Sdoi2016]齿轮(并查集 启发式合并)

题意

题目链接

sol

和cc的一道题很像啊

对于初始的(n)个点，每加一条限制实际上就是合并了两个联通块。

那么我们预处理出(val[i])表示的是(i)节点所在的联通块根节点转了(1)圈，该节点会转多少圈

并查集维护联通性以及联通块大小，直接启发式合并就可以了

跑的好像还挺快

#include<bits/stdc++.h> #define siz(v) ((int)v.size()) using namespace std; const int maxn = 2001; const double eps = 1e-9; inline int read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n, m, fa[maxn], siz[maxn]; double val[maxn]; vector<int> v[maxn]; void init() {     for(int i = 1; i <= n; i++) fa[i] = i, v[i].clear(), siz[i] = 1, val[i] = 1; } int find(int x) {     return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); } bool dcmp(double x) {     return fabs(x) < eps; } void mem(int x, int fa, double va) {     for(int i = 0; i < siz(v[x]); i++) {         int to = v[x][i];         if(to == fa) continue;         val[to] *= va;         mem(to, x, va);     } } bool solve() {     n = read(); m = read(); bool flag = 0;        init();     for(int i = 1; i <= m; i++) {         int x = read(), y = read(), fx = find(x), fy = find(y); double vx = read(), vy = read();         if(flag) continue;         if(fx == fy) {if(!(dcmp(val[x] / val[y] - vx / vy))) flag = 1; continue;}         if(siz[fx] > siz[fy]) swap(x, y), swap(vx, vy), swap(fx, fy);         val[fx] = vx / vy * val[y] / val[x];         mem(fx, 0, val[fx]); fa[fx] = fy; v[y].push_back(fx);         siz[fy] += siz[fx]; siz[fx] = 0;     }     return flag ^ 1; } int main() { #ifndef online_judge     freopen("a.in", "r", stdin); #endif     int t = read();     for(int i = 1; i <= t; i++) {         printf("case #%d: ", i);         puts(solve() ? "yes" : "no");     }     return 0; } /* 2 3 3 1 2 3 5 2 3 5 -7 1 3 3 7 3 3 1 2 3 5 2 3 5 -7 1 3 3 -7 */