洛谷P4578 [FJOI2018]所罗门王的宝藏(dfs)
程序员文章站
2022-06-28 13:33:40
题意 "题目链接" Sol 对于每个询问$x, y, c$ 从在$(x, y)$之间连一条边权为$c$的双向边,然后就是解$K$个二元方程。 随便带个数进去找找环就行了 cpp include define LL long long define fi first define se second ......
题意
sol
对于每个询问\(x, y, c\)
从在\((x, y)\)之间连一条边权为\(c\)的双向边,然后就是解\(k\)个二元方程。
随便带个数进去找找环就行了
#include<bits/stdc++.h> #define ll long long #define fi first #define se second #define pair pair<int, int> #define fin(x) freopen(#x".in", "r", stdin); using namespace std; const int maxn = 3001, inf = 1e9 + 10; template<typename a, typename b> inline bool chmax(a &x, b y) {return x < y ? x = y, 1 : 0;} template<typename a, typename b> inline bool chmin(a &x, b y) {return x > y ? x = y, 1 : 0;} 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, val[maxn], vis[maxn]; vector<pair> v[maxn]; int dfs(int x) { vis[x] = 1; for(auto &to : v[x]) { if(vis[to.fi] && val[x] + val[to.fi] != to.se) return 0; else if(vis[to.fi]) continue; val[to.fi] = to.se - val[x]; if(!dfs(to.fi)) return 0; } return 1; } void solve() { memset(val, 0, sizeof(val)); memset(vis, 0, sizeof(vis)); int n = read(), m = read(), k = read(); for(int i = 1; i <= n + m; i++) v[i].clear(); for(int i = 1; i <= k; i++) { int x = read(), y = read(), c = read(); v[x].push_back({y + n, c}); v[y + n].push_back({x, c}); } for(int i = 1; i <= n + m; i++) if(!vis[i] && !dfs(i)) {puts("no"); return ;} puts("yes"); } signed main() { // fin(a); for(int t = read(); t--; solve()); return 0; }
上一篇: Ubuntu18.04安装ROS