为什么同样的内容用不同的写法得分不一样啊
查看原帖
为什么同样的内容用不同的写法得分不一样啊
182525
yangyujia18楼主2020/8/26 09:28
#include<bits/stdc++.h>
using namespace std;
int n,m,arr[100005];
long long a[100005],b[100005],s[100005],c[3];//cÊǶþ·Öͼһ²àµÄ×ÜºÍ 
vector<int> u,v,g[100005];
int fa[100005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	fa[x]=y;
}
bool dfs(int now,int col)
{
	arr[now]=col;
	c[col]+=s[now];
	bool flag=true;
	for(int i=0;i<g[now].size();i++)
	{
		if(arr[g[now][i]]==col)
			flag=false;
		if(arr[g[now][i]]==0&&!dfs(g[now][i],3-col))//就是这里如果直接把dfs的值赋值给flag就有几个点wa了
			flag=false;
	}
	return flag;
}
bool solve()
{
	for(int i=1;i<=n;i++)
		s[find(i)]+=b[i]-a[i];
	for(int i=0;i<u.size();i++)
	{
		int x=find(u[i]),y=find(v[i]);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		if(find(i)==i&&arr[i]==0)
		{
			c[1]=c[2]=0;
			bool isbin=dfs(i,1);
			if(isbin&&c[1]!=c[2])
				return false;
			if(!isbin&&((c[1]^c[2])&1))//ÓÃλÔËËãÊÇÒòΪ³ö¸ºÊýµÄ»°È¡Ä£»áÓÐÐþѧ´íÎó 
				return false;
		}
	return true;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int l;
	cin>>l;
	while(l--)
	{
		cin>>n>>m;
		memset(s,0,sizeof(s));
		memset(arr,0,sizeof(arr));
		for(int i=1;i<=n;i++)
		{
			fa[i]=i;
			g[i].clear();
		}
		u.clear();
		v.clear();
		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 opt,x,y;
			cin>>opt>>x>>y;
			if(opt==1)
			{
				u.push_back(x);
				v.push_back(y);
			}
			else
				unite(x,y);
		}
		if(solve())
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
2020/8/26 09:28
加载中...