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

题解

发现似乎相当于问一个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('
')
#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[2005],sumE,num[2005];
bool vis[2005];
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 ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}