题意
题目链接
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 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606085.html