【CF1537F】Figure Fixing（思维）

题意：给一张图，每个点有一个可以为负的权值 \(a_i\)，一次操作可以选择一条边 \((i,j)\) 并让 \(a_i,a_j\) 同时增加任意一个可以为负的整数值，问是否存在操作方式使得所有点点权变为 \(0\)。

首先判掉 \(\sum a_i\) 为奇数的情况。

由于逆操作的存在，那么我们可以对于原来的条件任意操作，而不影响答案。

那么我们可以先通过一些操作把题目转化为更加简单的等价题目。

考虑现在图中随便找一棵生成树出来，那么我们可以自底向上地将所有点的权值都变为 \(0\)，根除外。

显然现在根的权值为偶数，若它不为 \(0\)，考虑将它的权值先 “平摊” 到另一个与它相连的点上，然后再将两个点同时加减使它们都变为 \(0\)。

若能找到一个奇环，我们就能实现上面的 “平摊”，直接输出 YES 即可。

否则若找不到奇环，考虑证明此时无论如何都不能满足条件。

注意到找不到奇环说明原图是二分图。假设根在左侧，发现无论如何操作，左边点的总权值-右边点的总权值都是不变的，等于一开始根的权值。也就是说不可能让所有点的权值都归零。

于是只需要判断原图是否存在奇环即可。

#include<bits/stdc++.h>

#define N 200010
#define ll long long

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}

int T,n,m;
int cnt,head[N],nxt[N<<1],to[N<<1];
bool vis[N],col[N];
ll a[N];

void adde(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

void dfs(int u)
{
	vis[u]=1;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(vis[v]) continue;
		dfs(v);
		a[u]-=a[v],a[v]-=a[v];
	}
}

bool find(int u)
{
	vis[u]=1;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(vis[v])
		{
			if(col[v]==col[u]) return 1;
			continue;
		}
		col[v]=col[u]^1;
		if(find(v)) return 1;
	}
	return 0;
}

int main()
{
	T=read();
	while(T--)
	{
		n=read(),m=read();
		cnt=0;
		for(int i=1;i<=n;i++) head[i]=vis[i]=col[i]=0;
		for(int i=1;i<=n;i++) a[i]=read();
		ll sum=0;
		for(int i=1;i<=n;i++) a[i]-=read(),sum+=a[i];
		for(int i=1;i<=m;i++)
		{
			int u=read(),v=read();
			adde(u,v),adde(v,u);
		}
		if(abs(sum)&1)
		{
			puts("NO");
			continue;
		}
		dfs(1);
		if(!a[1])
		{
			puts("YES");
			continue;
		}
		for(int i=1;i<=n;i++) vis[i]=0;
		puts(find(1)?"YES":"NO");
	}
	return 0;
}

原文地址：http://www.cnblogs.com/ez-lcw/p/16837411.html