题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4602
隔壁在讲莫比乌斯反演，但是我知道自己太菜了，并不能听懂，所以只能在这里刷水题QAQ
对于u->v的传动比为x/y
对于v->u的传动比为y/x
然后就大力dfs就好了，碰到矛盾的就退出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<bits/stdc++.h> #define maxn 1010 #define pb push_back #define eps 1e-8 #define db double using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int to; db num; node(int x,db y){to=x,num=y;} }; int T,n,m; vector<node>go[maxn]; db num[maxn]; inline void init(){ for(int i=1; i<=n; i++)go[i].clear(); memset(num,0,sizeof(num)); } bool dfs(int now){ for(int i=0; i<go[now].size(); i++){ int to=go[now][i].to; db x=go[now][i].num; if(!num[to]){ num[to]=num[now]*x; if(!dfs(to))return false; } else if(fabs(num[now]*x-num[to])>=eps)return false; } return true; } int main(){ T=rd(); for(int Case=1; Case<=T; Case++){ n=rd(),m=rd(); init(); while(m--){ int u=rd(),v=rd(),x=rd(),y=rd(); go[u].pb(node(v,1.0*x/y)); go[v].pb(node(u,1.0*y/x)); } bool can=true; for(int i=1; i<=n; i++){ if(!num[i]){ num[i]=1.0; can=dfs(i); if(!can)break; } } printf("Case #%d: ",Case); if(can)puts("Yes"); else puts("No"); } return 0; } |
