statement
https://acm.ecnu.edu.cn/contest/332/
E. Consistent Trading
题意:给定一张无向图,u 指向 v,边权为 w,表示 用 1 个 u 可以换 w 个 v,且 w 个 v也可以换 1 个 u。问是否可能换出无限多物品。
连接 (u,v,w) 以及 (v,u,w1)
从任意一点出发,如果转了一圈回来时该点权值变了,则说明产生了差价,也就说明可以换出无限多物品。
由于精度问题,不能用分数算,需要用逆元哈希判断相等。要找个好的模数。
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
| #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std; #define ll long long const int N = 2e6 + 10; const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 433494437; int n, m; struct E { int v; ll w; }; vector<E>G[N]; ll Pow(ll a, ll b) { ll res = 1; while (b) { if (b & 1)res = res * a%mod; a = a * a%mod; b >>= 1; } return res; } ll inv(ll a, ll mod) { return Pow(a, mod - 2); } int vis[N]; ll d[N]; void dfs(int u) { vis[u] = 1; for (E& e : G[u]) { int v = e.v; ll w = e.w; if (!vis[v]) { d[v] = d[u] * w%mod; dfs(v); } else if (d[v] != d[u] * w%mod) { puts("No"); exit(0); } } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; ll w; scanf("%d%d%lld", &u, &v, &w); G[u].push_back({ v,w }); G[v].push_back({ u,inv(w,mod) }); } for (int i = 1; i <= n; i++) { d[i] = 1; if (!vis[i])dfs(i); } puts("Yes"); return 0; }
|