链接
https://codeforces.com/contest/1537/problem/F
题意
给定一张包含 $n$ 个点 $m$ 条边的无向连通图，第 $i$ 个节点有当前权值 $v_i$ 和目标权值 $t_i$ 两种属性。
每次可以选择一条边 $(i,j)$，将 $v_i$ 和 $v_j$ 都增加任意整数 $k$。可以执行任意次上述操作。
判断能否将所有节点的 $v_i$ 都变为 $t_i$。
思路
每次操作都使两个点增加了 $k$，即 $\sum_{i=1}^n{v_i}$ 增加了 $2k$，那么当 $\sum_{i=1}^n{t_i-v_i}$ 不是偶数时，一定无解。
接下来分两种情况：
- 图是二分图：每次操作都使属于不同点集的两个点增加了 $k$，那么当两个点集的 $\sum{t-v}$ 相等时有解，否则无解；
- 图不是二分图：我们可以将点分成两个点集，这两个点集的 $\sum{t-v}$ 奇偶性一定相同，因为不是二分图，所以肯定存在一个点集里的两个点之间有边，那么可以对这条边操作，使两个点集的 $\sum{t-v}$ 相等，即一定有解。
代码
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
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=2e5+5;
int col[N],a[N],b[N];
VI g[N];
void init(int n) {
for(int i=1;i<=n;i++) {
col[i]=-1;
g[i].clear();
}
}
bool dfs(int u,int t) {
col[u]=t;
for(auto v:g[u]) {
if(col[v]==t) return false;
else if(col[v]==-1) if(!dfs(v,t^1)) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;cin>>T;
while(T--) {
int n,m;cin>>n>>m;
init(n);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<=m;i++) {
int u,v;cin>>u>>v;
g[u].PB(v),g[v].PB(u);
}
LL sum=0;
for(int i=1;i<=n;i++) sum+=b[i]-a[i];
if(sum&1) cout<<"NO"<<'\n';
else {
bool f=false;
for(int i=1;i<=n;i++) if(col[i]==-1) {
if(!dfs(i,0)) {f=true;break;}
}
if(f) cout<<"YES"<<'\n';
else {
LL sum[2];
sum[0]=sum[1]=0;
for(int i=1;i<=n;i++) sum[col[i]]+=b[i]-a[i];
cout<<(sum[0]==sum[1]?"YES":"NO")<<'\n';
}
}
}
return 0;
}
|