【LOJ】 #2520. 「FJOI」所罗门王的宝藏

题解

发现似乎相当于问一个2000个元的方程组有没有解……

然而我懵逼啊……

发现当成图论，两个点之间连一条边，开始BFS，每个点的值赋成边权减另一个点的点权

如果一个环不合法那么肯定无解

代码

#include <iostream>#include <cstdio>#include <vector>#include <algorithm>#include <cmath>#include <cstring>#include <map>#include <queue>//#define ivorysi#define pb push_back#define space putchar(' ')#define enter putchar('\n')#define mp make_pair#define pb push_back#define fi first#define se second#define mo 974711#define MAXN 2000005#define eps 1e-3#define RG register#define calc(x) __builtin_popcount(x)using namespace std;typedef long long int64;typedef double db;template<class T>void read(T &res) {res = 0;char c = getchar();T f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f;}template<class T>void out(T x) {if(x < 0) {putchar('-');x = -x;}if(x >= 10) {out(x / 10);}putchar('0' + x % 10);}struct node {int to,next,val;}E[4005];int head[],sumE,num[];bool vis[];int T,N,M,K;void add(int u,int v,int c) {E[++sumE].to = v;E[sumE].next = head[u];E[sumE].val = c;head[u] = sumE;}void addtwo(int u,int v,int c) {add(u,v,c);add(v,u,c);}queue<int> q;bool BFS(int x) {while(!q.empty()) q.pop();q.push(x);vis[x] = 1;num[x] = 0;while(!q.empty()) {int u = q.front();q.pop();for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(!vis[v]) {num[v] = E[i].val - num[u];vis[v] = 1;q.push(v);}else if(num[u] + num[v] != E[i].val) return false;}}return true;}void Init() {read(N);read(M);read(K);memset(head,0,sizeof(head));sumE = 0;memset(vis,0,sizeof(vis));int x,y,c;for(int i = 1 ; i <= K ; ++i) {read(x);read(y);read(c);addtwo(x,y + N,c);}}void Solve() {read(T);while(T--) {Init();bool ans = 1;for(int i = 1 ; i <= N + M ; ++i) {if(!ans) break;if(!vis[i]) ans &= BFS(i);}if(ans) puts("Yes");else puts("No");}}int main() {#ifdef ivorysifreopen("f1.in","r",stdin);#endifSolve();return 0;}