• 思维难度：提高+/省选-
• 实现难度：普及/提高-
• 推荐指数：8.5（推荐指数最高为10.0）

## 题目翻译

Figure Fixing

You have a connected undirected graph made of $n$ nodes and $m$ edges. The $i$-th node has a value $v_i$ and a target value $t_i$.

In an operation, you can choose an edge $(i,j)$ and add $k$ to both $v_i$ and $v_j$, where $k$ can be any integer. In particular, $k$ can be negative.

Your task to determine if it is possible that by doing some finite number of operations (possibly zero), you can achieve for every node $i$, $v_i=t_i$.

## 题解

#include<stdio.h>
#define MAXN 200005
#define MAXM 200005
typedef long long ll;
struct node{
int eh;
int v;
int c;
}V[MAXN];
ll s[2];
struct edge{
int next;
int to;
}E[MAXM*2];
int tot;
{
E[++tot]=(edge){V[from].eh,to};
V[from].eh=tot;
}
bool vis[MAXN],flag;
void dfs(int i,int c)
{
if(vis[i]&&V[i].c!=c)
{
flag=true;
return;
}
if(vis[i]) return;
V[i].c=c;
vis[i]=true;
s[c]+=V[i].v;
for(int p=V[i].eh;p;p=E[p].next)
{
dfs(E[p].to,c^1);
if(flag) return;
}
}
int main()
{
int i,T,n,m,t,x,y;
ll sum;
scanf("%d",&T);
while(T--)
{
sum=0;
tot=0;
s[0]=s[1]=0;
flag=false;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&V[i].v);
for(i=1;i<=n;i++)
{
scanf("%d",&t);
V[i].eh=0;
V[i].v-=t;
sum+=V[i].v;
vis[i]=false;
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
}
if(sum%2!=0)
{
printf("NO\n");
continue;
}
dfs(1,0);
if(flag||s[0]==s[1]) printf("YES\n");
else printf("NO\n");
}
return 0;
}

## 发送评论编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)

Emoji